LeetCode-268（Python）—— 丢失的数字

丢失的数字

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

输入：nums = [3,0,1]
输出：2
 
输入：nums = [0,1]
输出：2
 
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
 
输入：nums = [0]
输出：1

方法一：暴力循环

思路：简化思路，缺失数字为一个，所以总长度为 len(nums) + 1。然后暴力循环判断是否在原列表里面即可。

# 暴力循环
# 简化思路，缺失数字为一个，所以总长度为 len(nums) + 1。
# 然后暴力循环判断是否在原列表里面即可。
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for num in range(len(nums) + 1):
            if num not in nums:
                return num

方法二：排序+if大法

思路：此算法的精髓在于排序，对于头尾缺失情况直接返回即可。但是若中间缺失的话，前后依次相减，找到等于 2 的位置的值。

# 排序+if大法
# 此算法的精髓在于排序，对于头尾缺失情况直接返回即可。
# 但是若中间缺失的话，前后依次相减，找到等于2的位置的值。
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        if nums[-1] == len(nums) and nums[0] == 0:
            nums_new = [nums[i+1] - nums[i] for i in range(len(nums) - 1)]
            return nums_new.index(2) + 1
        if nums[-1] != len(nums):
            return nums[-1] + 1
        if nums[0] != 0:
            return 0

方法三：排序（优化版）

思路：排序以后，用 enumerate() 方法枚举列表，如果位置不等于值，返回即可。

# 排序（优化版）
# 排序以后，用 enumerate() 方法枚举列表，如果位置不等于值，返回即可。
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i,v in enumerate(nums):
            if i != v:
                return i
        return len(nums)

方法四：哈希集合

思路：set() 集合的特点是有序不重复，依次判断返回即可。

# 哈希集合
# set() 集合的特点是有序不重复，依次判断返回即可。
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums_s = set(nums)
        for i in range(len(nums) + 1):
            if i not in nums_s:
                return i

方法三：高斯求和

思路：数列求和与原列表和的差值即为缺失值。

# 高斯求和
# 数列求和与原列表和的差值即为缺失值。
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        return (n * (n + 1) // 2) - (sum(nums))

总结

请跟我一起复习高中等差数列求和知识：“首项加尾项乘以项数乘以二”。