LeetCode题解—260.只出现一次的数字Ⅲ

题目地址：260. 只出现一次的数字 III - 力扣（LeetCode）

题解：

这道题是基于寻找只出现一次的数字Ⅰ上的拓展。136. 只出现一次的数字 - 力扣（LeetCode）

 在Ⅰ中，我们只需要把所有的数字异或一遍即可，因为只有一个数字是唯一的。

但是，这道升级题中有两个单独的数字，只是异或遍历一遍的话就相当于让这两个数字异或。

这样是不能找到这两个数字的。因此我们的重点就是在异或之后，怎样才能把他俩分开。

首先，我们要清楚异或的“本质”。

异或两个数字，实际上就是二进制里它俩哪一位不同就是1，哪一位相同就是0。

而这，就是分离这两个数字的关键。

因为是两个不同的数字，所以注定它们至少有一位是不同的，该位的数值是1。

那么好了，我们可以把数组全部遍历一遍。这一位上是1的放一组，是0的放一组。

这样分组后，就决定了这两个数字肯定分在了两组。

于是，问题就回到了最初的情况，一组里只有一个数字是单独的，其他都是两个。

那么只需要把这两组再分别异或一遍即可。

这里我们可以举个例子：

第一步，全部异或，得到二进制表示为（因为数据不大，以下均展示4位）

5 ^ 2 = 0011

第二步，取任意一位为1的位数，这里我们选第一位。0011

第三步，将原数组按第一位分开，得到：

第四步，分别异或，得到答案。

代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //全部异或
        int num = 0;
        for(auto x : nums)
        {
             num ^= x;
        }

        //寻找第一个位数为1的位
        int pos = 0;
        for(pos = 0; pos < 32; pos++)
            if(num >> pos & 1) break;

        //将原数组依据该位遍历分开
        int left = 0, right = 0;
        for(auto x : nums)
        {
            if(x >> pos & 1) left ^= x;//该位为1
            else right ^= x;//该位为0
        }
        return {left, right};
    }
};

效率

当然，哈希也是一种解法，但哈希的空间复杂度太高，是O(N)。

而该方法的空间复杂度是O(1)。

同时，时间复杂度是O(N)。

不要降低预期去屈就性能，而要提升性能满足预期。——拉尔夫•马斯顿

如有错误，敬请斧正