用异或找-两个只出现一次的数

在这里插入图片描述如果是只有一个元素只出现一次，那么可以用异或抵消出现两次的元素，从而找出那个只出现一次的元素。

现在是恰好有两个元素只出现一次，那这道题的难点就在于：

如何把 “这两个只出现一次的元素” 拆分开，再分别用异或抵消出现两次的元素的方式，从而找出这两个只出现一次的元素。

1.计算所有数的异或结果

根据异或运算的性质，出现偶数次的数会互相抵消，最后剩下的就是两个奇数次的数的异或结果。

1
2
3
4


int eor1 = 0;
for (int num : nums) {
    eor1 ^= num;
}

2.用 Brian Kernighan 算法提取最右侧的 1

1

int rightOne = eor1 & (-eor1);

3.分组异或得到其中一个目标数

因为rightOne是a ^ b最右侧的 1，这意味着 a 和 b 在rightOne对应的位上，一个是 0，一个是 1，可以此作为依据进行分组。

1
2
3
4
5
6


int eor2 = 0;
for (int num : nums) {
    if ((num & rightOne) == 0) {
        eor2 ^= num;
    }
}

4.得到另一个目标数

1

return new int[] { eor2, eor1 ^ eor2 };

完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public static int[] singleNumber(int[] nums) {
    // 计算所有数的异或结果，得到 a ^ b
    int eor1 = 0;
    for (int num : nums) {
        eor1 ^= num; // 偶数次的数抵消，最后剩下 a^b
    }

    // 提取 eor1 二进制中最右侧的1
    int rightOne = eor1 & (-eor1);

    // 按 rightOne 分组，异或得到其中一个目标数 a
    int eor2 = 0;
    for (int num : nums) {
        // 判断 num 在 rightOne 对应的位上是否为0
        if ((num & rightOne) == 0) {
            eor2 ^= num; // 该组中偶数次的数抵消，剩下 a
        }
    }

    // 得到另一个目标数 b = a ^ (a^b) = eor2 ^ eor1
    return new int[] { eor2, eor1 ^ eor2 };
}