题解 | #缺失的第一个正整数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        n = len(nums)
        mp = dict()
        #哈希表记录数组中出现的每个数字
        for i in range(n):
            if nums[i] in mp:
                mp[nums[i]] += 1
            else:
                mp[nums[i]] = 1
        res = 1
        #从1开始找到哈希表中第一个没有出现的正整数
        while res in mp:
            res += 1
        return res

该题可以直接对列表升序然后查找，但是在列表中查询的某个数的时间复杂度是o(n),但是放入哈希表查询，查询的时间复杂度是o(1).

该解法时间复杂度和空间复杂度都是o(n)