1.题目

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

进阶：

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

示例：

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

提示：

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

2.思路

如果数组是有序的，我们很容易就可以求出丢失的那个数

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

哈希表

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

位运算
可以将结果的初始值设为 n，再对数组中的每一个数以及它的下标进行一个异或运算，即：

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

missing
=4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)
=(4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2
=0∧0∧0∧0∧2
=2

  1.     public int missingNumber(int[] nums) {
  2.         int missing = nums.length;
  3.         for (int i = 0; i < nums.length; i++) {
  4.             missing ^= i ^ nums[i];
  5.         }
  6.         return missing;
  7.     }

高斯求和公式

  1.     public int missingNumber(int[] nums) {
  2.         int expectedSum = nums.length*(nums.length + 1)/2;
  3.         int actualSum = 0;
  4.         for (int num : nums) actualSum += num;
  5.         return expectedSum - actualSum;
  6.     }