剑指40-数组中只出现一次的数字

位运算、哈希表

题目描述

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

解法1

遍历数组，用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>v;
        for (int i = 0; i < data.size(); i++)
            if (map[data[i]] == 1)
                v.push_back(data[i]);
        *num1 = v[0]; *num2 = v[1];
    }
};

解法2

1. 如果两个数字相同，那么他们异或的结果为0

   所以将所有数字异或，结果就是两个只出现一次的数字异或的结果

2. 那么如何分离这两个数字呢

   异或结果为1时，两个数字里对应的位肯定为1和0，所以找到异或结果为1的位置ret &= (-ret);

   假如ret = 1110 ， -ret = 0010 , 所以 i = 0010

3. 再和每个数字做与操作，如果为1，则异或到num1，不为1则异或到num2

总结下流程为：所有数组异或–>和反码与得到1的位置–>和每个数字与判断–>对应再异或

class Solution2 {
public:
    void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
        int ret = 0;
        for (const int k : data) ret ^= k;
        ret &= (-ret); //找ret二进制中为1的位置
        *num1 = 0, *num2 = 0;
        for (const int k : data) { //再分别异或一次
            if (k & ret) *num1 ^= k; 
            else *num2 ^= k;
        }
    }
};