56-Ⅰ数组中数字出现的次数

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

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

解题思路：

异或的定义：如果两个值相同，异或结果为 $0$，否则为 $1$。

异或有两个重要性质

因此可以有

回到题目，将数组中相同的数字进行异或，则可以消除掉所有出现两次的数字，最后会只剩下两个只出现一次的数字 $x$ 、$y$ 的异或结果 $xor$。

而 $xor$ 的二进制中为 1 的地方，就是 $x$ 和 $y$ 不同的地方。可以找到 $xor$ 中第一个为 $1$ 的地方，假设为 $bi$。

那么可以将整个数组分为两部分，一部分是 $bi$ 为 $1$ 的数字，一部分是 $bi$ 为 $0$ 的数字。而且这两个只出现一次的数字会分别划分到这两个部分中。

如何快速找到 $xor$ 的二进制中第一个为 $1$ 的地方（从右到左）？

通过 $n$ & $($~$n + 1)$ 这个运算过程，可以得到 $n$ 中第一个 $1$ 的位置。

假设 $n = 101010$，则 $n$ 取反后为 $010101$。此时 $n$ & ~$n = 0$， $~n + 1 = 010110$ ，则 $n$ & $($~$n + 1) = 000010$。

代码：

public int[] singleNumbers(int[] nums) {
    if (nums == null || nums.length == 0 || nums.length % 2 == 1) {
        return new int[0];
    }
    int xor = 0;
    for (int num : nums) {
        xor ^= num;
    }
    int m = xor & (~xor + 1);
    int x = 0, y = 0;
    for (int num : nums) {
        // 分组异或
        if ((num & m) != 0) {
            x ^= num;
        } else {
            y ^= num;
        }
    }
    // 其中没有两个不同的数字
    if (x == 0 && x == y) {
        return new int[0];
    }
    return new int[]{x, y};

复杂度分析

• 时间复杂度$O(N)$：线性遍历 $nums$ 使用 $O(N)$ 时间。
• 空间复杂度$O(1)$：辅助变量占用常数大小的额外空间。