🚩传送门：https://leetcode-cn.com/problems/missing-number/

题目

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题 ?

示例 1：

输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所有的数字都在范围 [0,3] 内。2 是丢失的数字，它没有出现在 nums 中。

示例 2：

输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所有的数字都在范围 [0,2] 内。2 是丢失的数字，它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所有的数字都在范围 [0,9] 内。8 是丢失的数字，它没有出现在 nums 中。

示例 4：

输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所有的数字都在范围 [0,1] 内。1 是丢失的数字，它没有出现在 nums 中。

解题思路一：排序

如果数组是有序的，那么就很容易知道缺失的数字是哪个了。

  1. 0 没有出现在数组的首位
  2. _n_ 没有出现在数组的末位
  3. 那么缺失的数字一定在 0 和 n 之间，线性时间内扫描这个数组。

复杂度分析

时间复杂度： 。

由于排序的时间复杂度为 ，扫描数组的时间复杂度为

空间复杂度：或者。

空间复杂度取决于使用的排序算法，根据是否进行原地排序（即不使用额外的数组进行临时存储）。

官方代码

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         //对数组进行排序
  4.         Arrays.sort(nums);
  6.         // 判断 n 是否出现在末位
  7.         if (nums[nums.length-1] != nums.length) {
  8.             return nums.length;
  9.         }
  10.         // 判断 0 是否出现在首位
  11.         else if (nums[0] != 0) {
  12.             return 0;
  13.         }
  15.         // 此时缺失的数字一定在 (0, n) 中
  16.         for (int i = 1; i < nums.length; i++) {
  17.             if (nums[i] != i) {
  18.                 return i;
  19.             }
  20.         }
  22.         // 未缺失任何数字（保证函数有返回值）
  23.         return -1;
  24.     }
  25. }

解题思路二：哈希表

我们可以直接查询每个数是否在数组中出现过来找出缺失的数字。

如果使用哈希表，那么每一次查询操作都是常数时间 O(1) 的。

复杂度分析

时间复杂度： 。

集合的插入操作的时间复杂度都是 ，一共插入了 个数，时间复杂度为 。集合的查询操作的时间复杂度同样是 ，最多查询 次，时间复杂度为 。因此总的时间复杂度为 。

空间复杂度：。

集合中会存储 个数，因此空间复杂度为 。

官方代码

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         Set<Integer> numSet = new HashSet<Integer>();
  4.         for (int num : nums) numSet.add(num);
  6.         for (int number = 0; number < nums.length + 1; number++) {
  7.             if (!numSet.contains(number)) {
  8.                 return number;
  9.             }
  10.         }
  11.         return -1;
  12.     }
  13. }

🚩解题思路二：位运算

由于异或运算（XOR）满足结合律，并且对一个数进行两次完全相同的异或运算会得到原来的数，因此我们可以通过异或运算找到缺失的数字。

在编写代码时，由于 [0..n][0..n] 恰好是这个数组的下标加上 nn，因此可以用一次循环完成所有的异或运算，例如下面这个例子：

下标 0 1 2 3
数字 0 1 3 4

就得到了缺失的数字为 2。

复杂度分析

时间复杂度： 。

假设异或运算的时间复杂度是常数的，共会进行 次异或运算，因此总的时间复杂度为 。

空间复杂度：。

算法中只用到了 的额外空间，用来存储答案。

官方代码

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         //missing初始为下标缺失的nums.length
  4.         int missing = nums.length;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             missing ^= (i ^ nums[i]);
  7.         }
  8.         return missing;
  9.     }
  10. }

😱解题思路二：数学

用 高斯求和公式 求出 [0.._n_] 的和，减去数组中所有数的和，就得到了缺失的数字。

高斯求和公式即：

  1. <br />在线性时间内求出数组中所有数的和，并在常数时间内求出前 `n+1` 个自然数（包括 0）的和，将后者减去前者，就得到了缺失的数字。

复杂度分析

时间复杂度： 。

求和的时间复杂度为 ，高斯求和公式的时间复杂度为 ，因此总的时间复杂度为 。

空间复杂度：。

法中只用到了 的额外空间，用来存储答案。

官方代码

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         int expectedSum = nums.length*(nums.length + 1)/2;
  4.         int actualSum =  Arrays.stream(nums).sum();
  5.         return expectedSum - actualSum;
  6.     }
  7. }