分组异或，用异或运算筛选元素

题目链接-来源：力扣（LeetCode）

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

示例 1：

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

思路：

我们可以遍历数组，将所有数字都放到哈希表当中，而出现冲突时则删除。目标数字只出现一次，而其他数字重复出现后即删除。余下的数字即是我们需要的数字。但是这样的话空间复杂度为 O(n)，不符合题目要求。
信号处理中，位运算常常用来帮助我们进行信号的筛选。我们考虑进行位运算中的「异或」（xor）运算，「异或」具有一个优良性质：进行「异或」运算的元素中，如果有相同的元素成对出现，它们会互相抵消，对其余元素没有任何影响。
而本题中，无关元素恰好都是出现2次，成对出现。于是我们只要考虑将数组中所有元素依次进行「异或」操作，就能过滤掉它们，留下我们需要的两个数字的异或结果，记为 xor，这两个数字我们记为 a 和 b。
接下来我们考虑如何分离这对数字。
由于 xor 存储了 a ^ b ，xor 中任何一位为 1 表示 a 与 b 在这一位不同，为 0 则表示相同。于是我们可以找到任意为 1 的一位，用以区分 a 与 b。这样，我们再次遍历数组，进行「分组异或」：

  • 我们保留 xor 中为 1 的某一位，将其余位置0，记为 digit，这个 digit 称为「掩码」，当元素与 digit 进行「与」运算后，会根据这一位为 1 或是 为 0 被分为 2 组。a，b 自然会被分在 2 组当中，而其余元素，不论如何分配，分在某一组中的元素一定是成对出现的，这样在「异或」操作中仍然会被消除。
  • 获取 digit 的方法有很多，比如按任意方式遍历 xor，当某位为 1 时停止。可以将 digit 初始至为 1，不断进行左移操作，直到 digit & xor = 1 时停止，这样 digit 就是我们所需的「掩码」。
  • 再次遍历 nums，用两个变量 a 和 b 分组存储异或结果，每个元素根据与 digit「与」的结果被分配给 a 或者 b进行异或。最后的 a、b即为所求答案。

时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] singleNumbers(int[] nums) {
        int xor = 0;
        for (int item : nums) {
            xor ^= item;
        }
        
        int digit = 1;
        while ((digit & xor) == 0) {
            digit <<= 1;
        }
        
        int a = 0, b = 0;
        for (int item : nums) {
            if ((digit & item) == 0) {
                a ^= item;
            } else {
                b ^= item;
            }
        }
        
        return new int[]{a, b};
    }
}