signed

QiShunwang

“诚信为本、客户至上”

位运算(数组中只出现一次的数字)

2021/5/14 23:11:58   来源:

算法学习笔记3–位运算

文章目录

  • 一、数组中只出现一次的数字
    • 1.1 题目描述
    • 1.2 思考
    • 1.3 代码实现
      • 1.3.1 哈希表
      • 1.3.2 位运算-异或


一、数组中只出现一次的数字

1.1 题目描述

在这里插入图片描述

1.2 思考

顺序扫描数组也可以得到结果,但是时间复杂度O(n^2),显然不是题目的目的。其次考虑哈希表哈希表统计数字出现的次数,最后对得到的结果进行排序输出,使用了辅助空间,空间复杂度增加,题目中的条件也没有完全利用上。
要利用上“数组中除了两个数只出现一次,其他数均出现两次”的条件,可以联想到异或。
异或(^),即相同为0,不同为1,设a,b为任意两个数:
1、相同两数异或为0(a^a = 0);
2、0与任何一个数异或为该数本身(a^0=a)。
3、且异或符合交换律(a^b =b^a)。

此处引用gzshan的思路说明:
我们先来看一个比较简单的情况,如果数组中只有一个数字出现一次,其他都出现两次。那么我们应该可以想到异或运算。异或运算有一个比较好的性质是:相同为0,相异为1。也就是说,任何一个数字异或它自己都等于0,而0异或任何数都等于那个数。因此,我们从头到尾依次异或数组中的每个数字,那么最终结果刚好是那个只出现一次的数字,重复的数字在异或过程中被抵消了。

这是一种比较巧妙的思路,然而,本题只出现一次的数字有两个,简单的异或无法解决。但是,借助这种思路,我们可以进一步分析,如果我们能把数组分成两个子数组,使每个子数组包含一个只出现一次的数字,而其他数字成对出现,那么我们通过上述解法就可以找到两个元素。

具体思路是:我们首先仍然从前向后依次异或数组中的数字,那么得到的结果是两个只出现一次的数字的异或结果,其他成对出现的数字被抵消了。由于这两个数字不同,所以异或结果肯定不为0,也就是这个异或结果一定至少有一位是1,我们在结果中找到第一个为1的位的位置,记为第n位。接下来,以第n位是不是1为标准,将数组分为两个子数组,第一个数组中第n位都是1,第二个数组中第n位都是0。这样,便实现了我们的目标。最后,两个子数组分别异或则可以找到只出现一次的数字。

举例:

以{2,4,3,6,3,2,5,5}为例:

我们依次对数组中的每个数字做异或运行之后,得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1,于是我们根据数字的倒数第二位是不是1分为两个子数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1,而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别两个子数组求异或,就能找到第一个子数组中只出现一次的数字是6,而第二个子数组中只出现一次的数字是4。

1.3 代码实现

1.3.1 哈希表

用哈希表统计数字出现的次数,最后对得到的结果进行排序输出,使用了辅助空间。
时间复杂度:O(n)
空间复杂度:O(n)
代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        vector<int> res;
        if(array.size() == 0) return res;
        map<int,int> m;
        for(int val : array){
            if(!m[val]) m[val] = 1;
            else m[val] += 1;
        }
        for(int val : array)
            if(m[val] == 1) res.push_back(val);
        sort(res.begin(),res.end());
        return res;
    }
};

运行结果如下:
在这里插入图片描述

1.3.2 位运算-异或

时间复杂度:O(n)
空间复杂度:O(1)

代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        vector<int> res(2);
        if(array.size() == 0 || array.size() == 1) return res;
        int tmp = 0;
        for(int val : array) tmp ^= val;
        int index = 0;
        for(;index<32;index++){
            if(((tmp>>index)&1)==1) break;
        }
        res[0] = 0;
        res[1] = 0;
        for(int val : array){
            if(((val>>index)&1)==1) res[0] ^= val;
            else res[1] ^= val;
        }
        if(res[0] > res[1]) swap(res[0],res[1]);
        return res;
    }
};

运行结果如下:

在这里插入图片描述

运行成功。