【剑指Offer】数组中只出现一次的数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路 1:利用 Map 存储次数,最后遍历 map 拿出次数为 1 的数字

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
            map<int, int> _map;
            for (int i = 0; i < data.size(); i++) {
                _map[data[i]]++;
            }
            vector<int> nums;
            map<int, int>::iterator iter = _map.begin();
            while (iter != _map.end()) {
                if(iter->second == 1)
                    nums.push_back(iter->first);
                iter++;
            }
            *num1 = nums[0];
            *num2 = nums[1];
    }
};

思路 2:位运算的性质

  • 数字和自己本身异或为 0(相同为 0,不同为 1)(&相同为 1 不同为 0,不进位)
  • 0 和任何数字异或为这个数字

所以先将所有数字异或可以得到最后两个数字异或的结果,再从低往高找差异位,再进行分组。

1, 1,2,2,3,4,5,5

001,001,010,010,011,100,101,101

全部异或得到:111,最低位为第 1(即 两个数从此出现差异)。3 和 4 分别最低位为 1 和 0,正好分到了 xx1 和 xx0 两个组,分组,组内再异或即可得到 3 和 4。

class Solution {
public:
    // 为1的最高位
    // 右移的过程中判断最低位
    int findFirst1(int bitResult){
        int index = 0;
        while(index < 32 && ((bitResult & 1) == 0)){
            bitResult >>= 1;
            index++;
        }
        return index;
    }
    
    // 某位是否为1
    bool isBit1(int target, int index){
        return ((target >> index)&1) == 1;
    }
    
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int bitResult = 0;
        for(int i = 0; i < data.size(); i++){
            bitResult ^= data[i];
        }
        // 得到 num1 和 num2 异或的结果,求最高位1的位置1001为4
        int index = findFirst1(bitResult);
        // 分组,最高位为1和不为1的分组,异或之后的结果
        for(int i = 0; i < data.size(); i++){
            if(isBit1(data[i], index))
                *num1 ^= data[i];
            else
                *num2 ^= data[i];
        }
    }
};

本文链接:https://ariser.cn/index.php/archives/397/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!