数组中只出现一次的两个数字

思路

设两个数字分别为 x，y

1. 将所有数字异或起来，得到的结果设为 s，s=x^y
   • 因为相同两个数字，异或结果为 0，由于异或运算满足交换律，因此最后就剩两个数字异或
2. 从 s 的二进制表示中，找到任意为 1 的位 k
   • xy 的二进制表示在第 k 位上，一个是 0，一个是 1
   • 因为 xy 不同，因此 s 不为 0，一定能找到k
3. 将数组中所有数根据第 k 位二进制是否为 1划分成两类；xy 分别位于不同的两类
4. 对于每一类，问题转换为：找出数组中唯一出现一次的数
   • 将所有数字异或起来，得到的结果就是唯一出现一次的数字
5. 找出任意一类的 x，即可算出 y：
   • 已知 x^y=s; 则 s^x=x^y^x=y;

代码

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int s=0;
        for(auto i:nums)
            s^=i;
        int k=0;
        while(!(s>>k&1))  k++;
        int x=0;
        for(auto i:nums)
            if(i>>k&1)  x^=i;
        return {x,s^x};
    }
};