题目

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

进阶：

  • 能否实现线性时间复杂度、仅使用额外阐述空间的算法解决此问题？

image.png

思路

思路一：排序后扫描整个数组

  1. class Solution:
  2.     def missingNumber(self, nums):
  3.         nums.sort()
  5.         # Ensure that n is at the last index
  6.         if nums[-1] != len(nums):
  7.             return len(nums)
  8.         # Ensure that 0 is at the first index
  9.         elif nums[0] != 0:
  10.             return 0
  12.         # If we get here, then the missing number is on the range (0, n)
  13.         for i in range(1, len(nums)):
  14.             expected_num = nums[i-1] + 1
  15.             if nums[i] != expected_num:
  16.                 return expected_num
  1. class Solution:
  2.     def missingNumber(self, nums: List[int]) -> int:
  3.         nums.sort()
  4.         for i, num in enumerate(nums):
  5.             if i != num:
  6.                 return i
  7.         return len(nums)

思路二：哈希表

可以直接查询每个数是否在数组中出现过来找出缺失的数字。如果使用哈希表，那么每一次查询操作都是常数时间的。

  1. class Solution:
  2.     def missingNumber(self, nums):
  3.         num_set = set(nums)
  4.         n = len(nums) + 1
  5.         for number in range(n):
  6.             if number not in num_set:
  7.                 return number

思路三：位运算

  • 异或：不同为1，相同为0。
  • 0异或任何数都为任何数。
  • 异或运算（XOR）：对一个数进行两次完全相同的异或运算会得到原来的数。a 异或 b 异或 b = a 异或 0 = a

image.png

  1. class Solution:
  2.     def missingNumber(self, nums):
  3.         missing = len(nums)
  4.         for i, num in enumerate(nums):
  5.             missing ^= i ^ num
  6.         return missing

思路四：数学

image.png

  1. class Solution:
  2.     def missingNumber(self, nums):
  3.         expected_sum = len(nums)*(len(nums)+1)//2
  4.         actual_sum = sum(nums)
  5.         return expected_sum - actual_sum