数组中只出现一次的两个数字（C++）

  一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围：数组长度2≤n≤1000，数组中每个数的大小 0 要求：空间复杂度 O(1)，时间复杂度 O(n)

提示：输出时按非降序排列。

输入：
[1,4,1,6]
返回值：
[4,6]
说明：
返回的结果中较小的数排在前面

输入：
[1,2,3,3,2,9]
返回值：
[1,9]

哈希思想即可。

class Solution {
public:
    
    vector FindNumsAppearOnce(vector& array) {
        int visited[1000001] = {0};
        vector res;
        for(int i = 0;i < array.size();i++)
            visited[array[i]]++;
        for(int i = 0;i < 1000001;i++)
            if(visited[i] == 1)
                res.push_back(i);
        return res;
    }
};

使用异或运算，异或运算有以下几个特点：

1. 两数相同为0，两数不相同为1。
2. 异或运算满足交换律和结合律，即a^b^a = (a^a)^b = 0^b = b。

那么如果我们有三个数，如果其中两数相同，我们根据异或运算的特点可以求出其中与另外两数不相同的那个数，如果n位数，其中有两位数不相同，其它数总会出现两次，我们也可使用异或运算求得两个不相同数的异或值。

例如，将数组[4, 1, 2, 1, 2]的第一项与之后的元素进行位运算。

4^1^2^1^2 = 100 ^ 101 ^ 111 ^ 110 ^ 100 = 4

化简后可得

4^(1^1)^(2^2) = 100 = 4

class Solution {
public:
    
    vector FindNumsAppearOnce(vector& array) {
        //结果值
        vector res(2,0);
        int XOR = 0;
        //对整个数组进行异或运算，求得两个不相同数的异或值
        for(auto x:array)
            XOR ^= x;
        int m = 1;//用于区分两个数
        //找到不相同数种二进制上从右往左第一个1，该位置上能保证两数二进制肯定时不同的，我们可以利用该位将两数进行分离
        while(!(m&XOR))m<<=1;
        for(auto x:array)
        {
            //如果与m的二进制上与运算相同的我们放入res[0]中
            if(!(m&x))res[0]^=x;
            else
                res[1]^=x;
        }
        //根据题目要求由小到大。
        if(res[0]>res[1])swap(res[0],res[1]);
        return res;
    }
};