LeetCode260.只出现一次的数字 III（位运算）

​​点击阅读更多查看文章内容

LeetCode260.只出现一次的数字 III（位运算）

题目传送门

一、题目解析

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

题意很简单不再赘述，比较容易想到的一种方法是用哈希表来存储每个数字出现的次数，然后遍历一边哈希表找到两个只出现一次的即可，但是本题还要求仅使用常数空间复杂度来实现，此时就需要用到另一种方法——位运算。

二、位运算

首先我们观察数组，除了两个仅出现一次的元素外，其他所有元素都是出现两次的，我们可以想到异或运算的性质——两个相同的数异或结果为0，且任何数和0异或都不变，那么我们可以将数组全部元素异或起来，得到的最终结果即为两个仅出现一次的元素的异或记为x。

得到两元素的异或后，我们进一步考虑，因为两元素不同，那么x肯定不会为0，至少有一位是为1，根据异或运算的性质，只有当两数不同时异或结果才会为1，我们可以通过x&-x求得x中最低位的1（求解原理在文章最后）记为y。

至此，我们可以得知要求的两个数在第y位上数字不同，一个为0，一个为1。我们可以将原数组分成两部分，分别是第y位上数字为0，和第y位上数字为1，此时这两部分分别包含两解，以及若干个两两相同的数。将这两部分分别异或，即可求得两解。

三、代码

注意溢出问题

class Solution
{
public:
    vector<int> singleNumber(vector<int> &nums)
    {
        int x = 0;
        for (int i : nums)
        {
            x ^= i;
        }
        int y = x & -x;
        int a = 0, b = 0;
        for (int i : nums)
        {
            if (i & y)
                a ^= i;
            else
                b ^= i;
        }
        vector<int>ret;
        ret.push_back(a);
        ret.push_back(b);
        return ret;
    }
};

关于x&-x的结果为何是最低位1，可参考如下博客
https://blog.csdn.net/oyoung_2012/article/details/79932394