【位运算】数组中只出现一次的两个数字

题目

73. 数组中只出现一次的两个数字

---

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

数据范围

数组长度 $[1,1000]$。

样例

输入：[1,2,3,3,4,4]

输出：[1,2]

解题

方法一：位运算

思路

设这两个落单的数分别是 $a, b$，首先类似 【位运算】只出现一次的数字 把数组中所有数字异或起来可以得到两个落单数异或的结果，也就是：$nums[1] \oplus nums[2] \oplus ... \oplus nums[n-1] = allXor = a \oplus b$，此时只需要求出其中一个落单的数就可以得到另一个数。

我们都知道异或运算得到的数的非零位就是这两个数不同的位，那么取到其中一个数与另一个数的不同位然后在 $nums$ 中找到与该数该位相同的所有数再异或起来得到的就是其中的一个落单的数，来看一个例子：

nums=[5,5,6,7,9,9,7,3,3,2] ：
把所有的数异或起来得到 $allXor=4(100_{(2)})$，然后取出其最低的非零位：$mask = 100_{(2)}$，然后把数组中所有第 $2$ 位是 $1$ 的数异或起来：$a = 5(101_{(2)}) \oplus 5(101_{(2)}) \oplus 6(110_{(2)}) \oplus 7(111_{(2)}) \oplus 7(111_{(2)}) = 6(110_{(2)})$ 这里拿到的 $6$ 就是一个落单的数，然后把该数与 $allXor$ 进行异或运算就得到了另一个落单的数。

代码

class Solution {
    public int[] findNumsAppearOnce(int[] nums) {
        int allXor = 0;
        for (int num : nums) allXor ^= num;
        int mask = allXor & -allXor;
        int a = 0;
        for (int num : nums) {
            if ((num & mask) != 0) a ^= num;
        }
        return new int[]{a, allXor ^ a};
    }
}