算法题:只出现一次的数字

最近看到了一个很有启发性的题目:

一个 int 类型的数组,除了【某两个】数字只出现了一次以外,其他数字均恰好出现了两次,找出这两个只出现一次的数。

当然,乃只能用常数级的额外空间(不然用哈希表计数就好了,还做个毛)。

——Leetcode 第 260 题

如果出现一次的数字只有一个,那么显然直接把全部数字求异或(符号用 ⊕ 来表示)即可得出。现在有两个单独的元素(假设为 a 和 b),那么全部异或的结果就变成了 a ⊕ b。如何得到 a 和 b?

由于 a ≠ b,所以 a ⊕ b ≠ 0。也就是至少有一位是 1,如果我们任取其中为 1 的位,那么 a 和 b 分别与之异或后,一定有一个结果为 0,而另一个结果不为 0。对于数组中的每一个数字,我们检查这位是否为 1,为 1 的分到一组,为 0 的分到另一组。这样,a 和 b 必然被分到了不同的两组,其他相同的数字也必定被分到了同一组。酱紫的话,这两个数组就都变成了只有一个不重复的数字了。

所以,我们的算法步骤如下:

  1. 对数组的全体元素求异或,得出的结果为 a ⊕ b。
  2. 任取 a ⊕ b 中不为 0 的位,其他位置为 0,令这个数为 mask。
  3. 针对数组中的每个数字,与 mask 求“与”(AND)操作,结果为 0 的分为 A 组,不为 0 的分为 B 组。
  4. 按照上面的结论,a 和 b 必然被分在了不同的组里。此时我们对每组中的元素分别求异或,则两组数字最终的结果就是 a 和 b。

在实际编码过程中,我们并不需要真的将元素分到两个集合里面(这样的话空间复杂度就变成 O(n) 啦,还不如直接用哈希表计数),只需要计算与 mask 求与运算的结果不为 0 的数字,得到其中一个只重复一次的数。由于我们已经求出了 a ⊕ b,所以与 a ⊕ b 再次异或就可以求出另一个数。

那么这个 mask 怎么求呢?比较简单的方法是写一个循环遍历每一位,找到不为 0 的位即可(以下代码中,aXb 表示 a ⊕ b 的结果):

            int mask = 1;
            for (int i = 0; i < 32; i++)
            {
                if ((aXb & mask) != 0) break;
                mask <<= 1;
            }

一个更好的办法是利用补码来求出(请自行脑补相关知识):

mask = aXb & (-aXb)

酱紫的话,代码就一气呵成啦:

    public int[] singleNumber(int[] nums) {
        // 1. 求出 a ⊕ b
        int aXb = 0;
        for (int num : nums) aXb ^= num;

        // 2. 取 a ⊕ b 的最右不为 0 的位,取其他不为 0 的位也可
        int mask = aXb & (-aXb);

        // 3. 将数组中有与 mask 相同位的数字分到一组,求异或,得出 a 或 b 其中之一
        int a = 0;
        for (int num : nums) {
            if ((num & mask) != 0)
                a ^= num;
        }

        // 4. 则 b 为 a ⊕ (a ⊕ b)
        return new int[] {a, a ^ aXb};
    }
有任何想法?请发邮件告诉老夫:daozhihun@outlook.com