【LeetCode260】只出现一次的数字 III（分组是关键，位运算）

一、题目

二、思路

如果我们把数组分成两个子数组，每个数组都满足「恰好有一个元素只出现一次，其余所有元素均出现两次」，就可以按照之前的方法直接解决了。

（1）直接遍历一遍数组并逐一【异或】一定可以得到那两个不同元素的异或。如数组[2,2,1,1,3,4]。这个数组的异或值最终是3 与 4 的异或值为 div = 0011 ^ 0100 = 0111。

（2）取最低位置的 ‘1’来进行对 a 与 b 的分组

div &= -div;

-div = 1000 + 0001 = 1001 （将div所有的bit反过来加1）

因此我们有 div & -div = 0111 & 1001 = 0001

（3）取得了最低为的 1 后可与进行对数组的分组，对于在 000 ‘1’这个位置有 1 的数字为一组，反之另一组，栗子中的具体分组过程：

数字 1 和 3 对应的值为 0001 与 0011，注意他们在最低位置都有0001，因此 div & 1 跟 div & 3 都会返回0001；数字 2 和 4 对应的值为 0010 与 0100 注意他们在最低位置都有没有0001，因此 div & 2 跟 div & 4 都会返回0000。

分成2个组后，每个数组里只有一个与众不同的数了，这样就回到【LeetCode136】只出现一次的数字（不能用哈希，用位运算-异或）的做法了。

三、代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long div = nums[0];
        for(int i = 1; i < nums.size(); i++){
            div ^= nums[i]; //异或
        }
        int a = 0, b = 0;
        //取最低位的1
        div &= -div;
        for(int i = 0; i < nums.size(); i++){
            if(div & nums[i]){
                a ^= nums[i];
            }else{
                b ^= nums[i];
            }
        }
        return {a, b};
    }
};