问题

数组中有两个数字只出现一次，其他数字都出现了两次，请找出出现一次的两个数字

要求复杂度：

时间：$O(N)$，空间：$O(1)$

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

算法：分组异或

容易想到将数组整体异或一遍得到两个出现一次数的异或值。

难点是怎么把这两个数分离出来？

容易想到分别异或这两个数就能分离。

难点是怎么分别异或这两个数呢？

那就是用分组异或啦！

我们希望将数组分成两组，且这两个数分到不同的组。分成两组可以和一个二进制只有1位是1的数与运算实现。

那么要哪一位是1呢？当然是两个数不同的那一位啦，因此答案就在刚刚我们异或得到的结果中！异或的结果中刚好就存储了两个数不同位！为了方便我们取最低位即可，用lowbit()实现。

复杂度

时间：$O(N)$
空间：$O(1)$

代码

class Solution {
public:
    int lowbit(int x){
        return x & -x;
    }
    vector<int> singleNumbers(vector<int>& nums) {
        int yh = 0;
        for(auto x: nums) yh ^= x;
        int mask = lowbit(yh);
        vector<int> ans(2, yh);
        for(auto x: nums){
            if((x & mask) == 0) {
                ans[0] ^= x;
            }
            else{
                ans[1] ^= x; 
            } 
        } 
        return ans;
    }
};