题目描述

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

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

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

样例

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

输出：[1,2]

算法1

(异或+思维) $O(n)$

1.所有数字异或之后假设是$res,res = x \bigoplus y$,假设$x,y$是只出现一次的数字
2.看$res$的二进制表示某一位不是0而是1，假设二进制表示第k位是1
因为$res = x \bigoplus y$那么第k位的1要么是x来的，要么y来的，异或：同零异一
3.遍历nums，把第k位是1分为一个集合，是0的是另一个集合。并把每个集合内的元素异或起来，两个集合的最终
结果就是答案。因为相同的数字只会出现在一个集合。如果是出现两次的异或之后相等于0了，剩下的就是答案了

时间复杂度

只遍历了numbs，复杂度是 $O(n)$

C++ 代码

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int res = 0;
        vector<int> v;
        // 把所有出现两次给过滤了
        for(int i = 0;i < nums.size();i++)
        res ^= nums[i];

        int k = 0;
        while(!((res>>k)&1)) k++;

        int x = 0,y = 0;
        for(auto it:nums){
            if((it>>k)&1) x ^= it;
            else y ^= it;
        }

        v.push_back(x);
        v.push_back(y);
        return v;
    }
};