[leetcode]260.只出现一次的数字（3）

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
           

示例 2：

输入：nums = [-1,0]
输出：[-1,0]
           

示例 3：

输入：nums = [0,1]
输出：[1,0]
           

提示：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次
           

思路：位运算

如果只有一个不同的数字，即题[leetcode]136.只出现一次的数字，从头到尾遍历数组进行异或，成对出现的会两两抵消掉，最后剩下的就是只出现了一次的数。

如果有两个只出现一次的数字，那么我们可以将所有的数字分成两组，使得：

1.两个只出现一次的数字在不同的组中。

2.相同的数字会被分到相同的组中。

分组策略：

1.对所有数字进行一次异或，会得到两个出现一次的数字的异或值。

2.在异或结果中找见一位非0位，则说明在该位上，一个数字为0，一个数字为1。

3.根据这一位数字进行分组，若是相同的数字也可以由于该位全为0或全为1分到一组

4.在每个组内再次进行全部异或，得到两个数字。

AC代码（C++）

class Solution {
   public:
    vector<int> singleNumber(vector<int>& nums) {
        int temp = 0, len = nums.size();
        for (int i = 0; i < len; i++) {
            temp ^= nums[i];  //从头到尾异或
        }
        int div = 1;  //记录异或结果中第一位为1的位
        int a = 0, b = 0;
        while ((div & temp) == 0) {
            div <<= 1;  //左移一位
        }
        for (int i = 0; i < len; i++) {
            //该位为1的分一组，为0的分另外一组
            if (div & nums[i]) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        return vector<int>{a, b};
    }
};