寻找丢失的数字

在这里插入图片描述这道题大多数人的第一反应是 “求和法”（用 0~n 的和减去数组总和），或者 “哈希表法”（存出现过的数再遍历查找）。

但今天本文要讲的异或解法，不仅时间复杂度和求和法一样是 $O (n)$，空间复杂度更是最优的 $O (1)$。

数组 nums 包含 [0, n] 中的 n 个数，理论上应该有n+1个数，实际上只有n个数，说明正好缺了一个。

也就是说：

完整的数字集合是：0, 1, 2, …, n（共 n+1 个数）；

数组中的数字集合是：完整集合去掉一个数（共 n 个数）。

想想看，如果我们把 “完整集合的所有数” 和 “数组中的所有数” 都做一次异或，会发生什么？

根据异或的性质：

完整集合和数组中都出现的数会互相抵消，最后剩下的，就是 “完整集合有、数组没有” 的那个数 —— 也就是我们要找的缺失数字。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public static int missingNumber(int[] nums) {
    // eorAll：存储 0~n 所有数的异或结果
    // eorHas：存储数组 nums 所有数的异或结果
    int eorAll = 0, eorHas = 0;

    for (int i = 0; i < nums.length; i++) {
        eorAll ^= i;       // eorAll 异或 0~nums.length-1
        eorHas ^= nums[i]; // eorHas 异或数组中的每个数
    }

    // 补全 eorAll，异或上 nums.length（因为完整集合是 0~n，循环漏了 n）
    eorAll ^= nums.length;

    // eorAll ^ eorHas = 缺失数字
    return eorAll ^ eorHas;
}