题解 | #数组中只出现一次的两个数字#

方法：异或运算

根据异或运算的性质，如果一个数组只有出现一次的数字，那么数组中所有的数字通过异或运算最终的结果就是该数字。

如果数组中有两个只出现一次的数字（target1、target2），我们首先就需要将targer1和target2区分开来。数组全部进行异或运算后最终的结果为target1 ^ target2，通过这个结果我们可以反推出target1和target2在哪些位上是不一致的，这样就可以将数组分为两类，分别进行异或运算得到target1和target2。

时间复杂度：o(n)。需要遍历数组

空间复杂度：o(1)。无额外辅助空间。

class Solution {
  public:
    vector<int> FindNumsAppearOnce(vector<int>& nums) {
        vector<int> res;
        int k = 1;
        int temp = 0;
        int res1 = 0;
        int res2 = 0;

        for (int i = 0; i < nums.size(); i++) {
            temp = temp ^ nums[i];
        }
		//找到两个数不相同的第一位
        while ((k & temp) == 0) {
            k <<= 1;
        }

        for (int i = 0; i < nums.size(); i++) {
		  	//分两类进行异或运算
            if (nums[i] & k)
                res1 = res1 ^ nums[i];
            else
                res2 = res2 ^ nums[i];
        }
		//按升序排列
        if (res1 > res2) {
            res.push_back(res2);
            res.push_back(res1);
        } else {
            res.push_back(res1);
            res.push_back(res2);
        }

        return res;
    }
};

此题也可通过哈希简单求解，但需要额外的辅助空间。