位运算&&剑指 Offer 56 - I. 数组中数字出现的次数

目标:查找出两个只出现一次的数字,其他数字都出现两次。
要求:时间复杂度O(n),空间复杂度O(1)。

1.起始代码(这里使用了哈希表,不符合题目要求)

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        vector<int>ans;
        map<int,int>m;
        for(auto x:nums){
            m[x]++;
        }
        for(auto y:m){
            if(y.second==1){
                ans.push_back(y.first);
            }
        }
        return ans;
    }
};

2.优化后的分组异或代码

知识点:相同数字异或等于0。
算法流程:
1)遍历nums执行异或,记录n=x^y;
2)循环左移m,m记录第1次x和y二进制不同的位置;
3)根据m记录的位置,拆分nums为两组;
4)这两组相互异或分别得到所求的两个数字。
5)返回这两个数字。
参考:剑指 Offer 56 - I. 数组中数字出现的次数(位运算,清晰图解)

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int m=0,n=1,x=0,y=0;
        for(auto num:nums){
            m^=num;
        }
        while(!(m&n)){
            n<<=1;
        }
        for(auto num:nums){
            if(n&num){
                x^=num;
            }
            else{
                y^=num;
            }
        }
        return {x,y};
    }
};
上一篇:剑指 Offer 56 - II. 数组中数字出现的次数 II


下一篇:56、什么是类的继承?