【剑指 offer】数组中只出现1次的2个数。

1、题目描述

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

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

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

样例：

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

2、问题描述：

3、问题关键：

• 异或运算，相同的数异或等于0；
• 异或之后，结果为只有出现1次的两个数的异或结果，结果的第k位不为0，那么，这两个数的第k位也不同（一个为1，一个为0），所以，将第k位为1的进行异或，那么就可以求出其中的一个数。
• 已知一个数，则再和原异或结果异或可以得到另外一个数。

4、C++代码：

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int a = 0;
        for (int i = 0; i < nums.size(); i ++) {
            a ^= nums[i];//最终得到的是只出现1次的2个数的异或结果。
        }
        int k = 0, b = 0;
        while(!(a >> k & 1)) k ++;//这两个数第k位是不同的。
        for (int i = 0; i < nums.size(); i ++) {
            if(nums[i] >> k & 1) 
                b ^= nums[i];//第k位为1的异或可以得到其中的一个数。
        }
        return vector<int> {b, b ^ a};
    }
};