题意

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

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

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

分析

法一：哈希表暴力
时空都是 $O(n)$

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        unordered_map<int, int> freq;
        vector<int> res;
        for(int x : nums){
            freq[x] ++;
        }
        for(int x : nums){
            if(freq[x] == 1)res.push_back(x);
        }

        return res;
    }
};

法二：位运算
首先考虑一个比较简单的退化版问题，如果一个数组中只有一个数出现一次，其他数都出现两次，那么要怎么求这个数？
方法很简单，就是求所有数的异或，出现两次的数与自身异或都会被抵消，最后剩下的就是只出现一次的数。
接下来考虑本问题，如果对所有数求异或，假设只出现一次的两个数是 x, y,那么得到的答案 s = x ^ y, 没办法得到分别是多少。因此，为了求解本问题，考虑转化为上面那个简单版的问题，要实现这个转换，就要把 x, y 分到两个不相交的集合中。考虑我们已有的信息 s = x^y, 我们可以得到 x^y 有哪些二进制位不同，因此，可以按照第一个不同的二进制位(第 k 位)为 1 还是为 0 进行分类，这样 x, y 就被分到了两个不同的集合，就可以按照上面简单版本的解法求解。
这个解法时间 $O(n)$, 空间 $O(1)$

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int sum = 0;
        for(int x : nums){
            sum ^= x;
        }
        int k = 0;
        for(k = 0; k < 32; k ++){
            if(sum>>k & 1)break;
        }
        int i = -1, j = nums.size();
        while(i < j){
            do i++; while(nums[i]>>k & 1);
            do j--; while(!((nums[j] >> k) & 1));
            if(i < j)swap(nums[i], nums[j]);
        }

        int left_sum = 0;
        for(i = 0; i <= j; i ++)left_sum ^= nums[i];
        vector<int> res;
        res.push_back(left_sum);
        res.push_back(sum ^ left_sum);

        return res;
    }
};