剑指 Offer 56 - I. 数组中数字出现的次数

题目内容

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

1 2	输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]

示例 2：

1 2	输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]

限制：

1	2 <= nums.length <= 10000

解法一：异或

由于要求时间复杂度是O(n)，空间复杂度是O(1)。
因此不能用 map（空间复杂度为 O(n) 与双重循环嵌套（空间复杂度为 O(n^2))

演示：
4 ^ 1 ^ 4 ^ 6 => 1 ^ 6

6 对应的二进制： 110
1 对应的二进制： 001
1 ^ 6 二进制： 111
此时我们无法通过 111（二进制），去获得 110 和 001。
那么当我们可以把数组分为两组进行异或，那么就可以知道是哪两个数字不同了。

通过 & 运算来判断一位数字不同即可分为两组，那么我们随便两个不同的数字至少也有一位不同吧！
我们只需要找出那位不同的数字mask，即可完成分组（ & mask ）操作。

由于两个数异或的结果就是两个数数位不同结果的直观表现，所以我们可以通过异或后的结果去找 mask！
所有的可行 mask 个数，都与异或后1的位数有关。

example	1	2	3
num1:	101110	110	1111
num2:	111110	001	1001
num1^num2:	010000	111	0110
可行的mask:	010000	001	0010
.		010	0100
.		100	.

为了操作方便，我们只去找最低位的mask:

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int sum = 0;
        for(auto num : nums){
            sum ^= num;
        }
        int flag = 1;

        while((flag & sum) == 0) flag <<= 1;

        vector<int> res(2);
        res[0] = res[1] = 0;
        for(int num:nums){
            if(flag & num) res[0] ^= num;
            else res[1] ^= num;
        }

        return res;


    }
};

结果

执行用时：
12 ms
, 在所有 C++ 提交中击败了
90.67%
的用户
内存消耗：
15.7 MB
, 在所有 C++ 提交中击败了
58.62%
的用户
通过测试用例：
35 / 35