剑指offer 61- 数组中只出现一次的两个数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

输入：[1,2,3,3,4,4]

输出：[1,2]

分析：

时间复杂度： 空间复杂度：

两个相同的数异或得0
两个不同的数（不为0）异或得1

令这两个不同数分别为和，异或的结果是s，则有 ^（与至少存在一位不同）
设中第位为，的第位为，的第位为

把nums中的所有数分成两大类，即第位为的所有数和第位为的所有数
则有：
第位为的所有数中(记为集合S1)，除了之外，其余所有数都出现2次；
第位为的所有数中(记为集合S2)，除了之外，其余所有数都出现2次；

集合S1中所有数异或，得到x
然后 ^
则的所有数异或起来就得到，和异或得到

class Solution {
public:

    vector<int> findNumsAppearOnce(vector<int>& nums) {
        /*vector<int> res;
        unordered_map<int, int> hash;
        for(auto x:nums) hash[x]++;
        for(auto x:nums) {
            if(hash[x] == 1) res.push_back(x);
        }
        return res;*/
        int sum=0;
        for(auto x:nums) sum^=x;
        int k = 0;
        while(!(sum>>k & 1)) k++;
        int X=0;
        for(auto x:nums) 
            if(x>>k & 1) X^=x;
        return {X, sum^X};
    }
};