268_丢失的数字

类型：数组

• 268. 丢失的数字 💚

  https://leetcode-cn.com/problems/missing-number/

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

  💡 排序

  排序后，先判断 0 是不是出现在首位，n 是不是出现在末位。

  扫描这个数组，如果某一个数比它前面的那个数大了超过 1，那么这两个数之间的那个数即为缺失的数字。

  class Solution:
      def missingNumber(self, nums):
          nums.sort()
  
          # 0 是否在首位
          if nums[-1] != len(nums):
              return len(nums)
          # n 是否在末位
          elif nums[0] != 0:
              return 0
  
          # 找到相邻差值大于 1 的数
          for i in range(1, len(nums)):
              expected_num = nums[i-1] + 1
              if nums[i] != expected_num:
                  return expected_num

  时间复杂度：O(NlogN)

  💡 哈希集合

  class Solution:
      def missingNumber(self, nums):
          num_set = set(nums)
          n = len(nums) + 1
          for number in range(n):
              if number not in num_set:
                  return number

  时间复杂度：O(n)，空间复杂度：O(n)

  💡 位运算

  a ⊕ a = 0，0 ⊕ a = a

  class Solution:
      def missingNumber(self, nums):
          missing = len(nums)
          for i, num in enumerate(nums):
              missing ^= i ^ num
          return missing

  时间复杂度：O(n)，空间复杂度：O(1)