题解 | 缺失的第一个正整数-哈希表

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#

class Solution:
    def minNumberDisappeared1(self , nums: List[int]) -> int:
        # write code here
        """
        设置哈希表存储每个数>0数
        1 如果数组填满1-n  缺失的为n+1 
        2. 如果数组填充不满缺失的是1-n 的数
         快速判断某个数是否出现过
        6/10 组用例通过 数组长度为100000超时
        """
        st=[]
        n=len(nums)
        mx=0 
        #print(n)
        for i in range(n):
            if nums[i]>0 and nums[i] not in st:
                st.append(nums[i])
                mx =max(mx,nums[i])
        for i in range(1,mx+2):
            if i not in st:
                return i 
        return 0  
    def minNumberDisappeared2(self , nums: List[int]) -> int:
        # write code here
        """
        设置哈希表存储每个数>0数
        1 如果哈希表填满1-n  缺失的为n+1 
        2. 如果哈希表填充不满缺失的是1-n 的数
         快速判断某个数是否出现过
        """
        dt=dict() # 使用哈希
        n=len(nums)
        mx=0 # 记录最大值用于后面遍历的范围
        #print(n)
        for i in range(n):
            if nums[i] in dt :
                dt[nums[i]]+=1
            else:
                dt[nums[i]]=1
            mx=max(nums[i],mx)
        for i in range(1,mx+2):
            if i not in dt:
                return i 
        return 0 
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        """
        设置哈希表存储每个数>0数
        1 如果哈希表填满1-n  缺失的为n+1 
        2. 如果哈希表填充不满缺失的是1-n 的数
         快速判断某个数是否出现过
        """
        dt=dict() # 使用哈希
        n=len(nums)
        for i in range(n):
            if nums[i] in dt :
                dt[nums[i]]+=1
            else:
                dt[nums[i]]=1
        res=1 # 从1开始判断
        while  res  in dt:
            res+=1
        return res