题解 | #数组中只出现一次的数字#

hash思路
map<int, int>用于记录元素和元素出现的次数
最后过滤出出现一次的两个元素

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int * arr[2] = {num1, num2};
        map<int, int> m;
        for(int i=0; i<data.size(); ++i)
            m[data[i]]++;
        int j = 0;
        for(map<int, int>::iterator it=m.begin(); it!=m.end(); ++it)
            if(it->second == 1)
                *arr[j++] = it->first;
    }
};

位运算

求出所有元素异或的值
拿出最右的1bit位
让所有与上一步的1bit位都是1元素的异或在一起，就得到其中一个数
然后这个数异或一下所有异或在一起的元素值就得到第二个数

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

        int xor_ = 0;
        for(int i=0; i<data.size(); ++i)
            xor_ ^= data[i];

        //求xor最右边的1bit位
        int right_1 = xor_&(~xor_+1);
        *num1 = 0;
        for(int i=0; i<data.size(); ++i){
            if(data[i]&right_1)
                *num1 ^= data[i];
        }
        *num2 = xor_^ *num1;
    }
};