前往此题

解题思路

预备知识

- 哈希表基础

解题思路 — 排序

题目给定的条件是一个**0-n的序列，也就是说排序后我们优先能检查0和n**是否不在该序列中，随后再通过遍历去检查其他数。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        if(nums[-1] != len(nums)): return len(nums)
        elif(nums[0] != 0): return 0

        for i in range(1, len(nums)):
            expect_num = nums[i-1] + 1
            if nums[i] != expect_num:
                return expect_num

复杂度分析

- 时间复杂度: O(N)

- 空间复杂度: O(N)

解题思路 — 哈希表

直接通过哈希表进行检查，需要注意的是最后一个n，如果正好缺失n的话，遍历条件必须是当前序列长度+1

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        num_set = set(nums)
        l = len(nums) + 1
        for n in range(l):
            if n not in num_set:
                return n

复杂度分析

- 时间复杂度: O(N)

- 空间复杂度: O(N)