LC260 Single Number III

本题链接：Single Number III

本题标签：Bit Manipulation

本题难度：

英文题目 中文题目

---

本题是136.Single Number的升级版。

方案1： 利用LC136的思路

根据LC136的思路，我们可以得到两个只出现一次的数字的异或结果，即例子中的。现在我们只要能将这个异或结果分离出来就能得到答案。那么我们可以从二进制的角度考虑，。

这里可以发现异或运算保留的是两个数不同的部分，若我们可以将 中最右边的 取出来组成 ，而这个就是数字3和数字5不同的部分，这样我们就可以通过和nums中的数进行二进制与运算是否为0来将nums划分为两部分，一部分包含了数字3和其他重复数字，另一部分包含了数字5和其他重复数字。

这个 我们可以通过异或结果与自己的负数进行二进制与运算得到，即。因为一个数的负数二进制形式是对这个数按位取反再加1，也就是补码形式。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2, 0);
        int diff = 0;
        for(int n : nums)
            diff = diff ^ n;
        diff = diff & (-diff); // 这里是为了保留diff中最右边为1的二进制位
        
        for(int n : nums)
        {
            if((n & diff) == 0)  // 根据与diff按位与是否为0将数组划分为两部分，
                                 // 这两部分各自包含一个只出现1次的数字
                res[0] = res[0] ^ n;
            else
                res[1] = res[1] ^ n;
        }
        return res;
    }
};

时间复杂度：

空间复杂度：

---