【Python】哈希之查找缺失正数

41. 缺失的第一个正数

https://leetcode.cn/problems/first-missing-positive/

暴力解法，直接哈希

思路：

• 边界情况，最大值小于1 or 最小值大于1，直接返回1

• 维护1个字典，存放所有的正整数，记录最小值和最大值

• if 最小值大于1，return 1

• 最大值 - 最小值 + 1 = len(dic)，return 最大值 + 1

• else 则中间有缺少的正整数，遍历最小值到最大值，返回不在dic中的正整数

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        min_, max_ = min(nums), max(nums)
        if min_ > 1 or max_ < 1:
            return 1
        dic = {}
        min_num, max_num = 1e20, 0
        for i in range(len(nums)):
            if nums[i] > 0 and nums[i] not in dic:
                dic[nums[i]] = None
                if nums[i] < min_num:
                    min_num = nums[i]
                if nums[i] > max_num:
                    max_num = nums[i]
        if min_num > 1:
            return 1
        if max_num - min_num + 1 == len(dic):
            return max_num + 1
        else:
            for i in range(min_num, max_num):
                if i not in dic:
                    return i

时间复杂度为O(n)，2次n的遍历，空间复杂度为O(n)，维护了一张哈希表