leetcode刷题日记-缺失的第一个正数（困难）

题目描述

解题思路

题目的意思十分容易理解，但是确实思考出来这种解题的方法还是比较难的。首先能想到的点就是[1,N]这个范围，因为只有N个数字，最小的数字只能在这个区间和N+1两种可能。但是有时间复杂度的限制，我们该怎么找。我们可以另外申请一块存储空间N+2大小，将出现在[1,N]这个区间的数字进行计数，然后从头开始遍历新开辟的存储空间，从1开始到N+1这个下标结束。中途如果出现计数的个数为0，那么直接返回下标即为最小的数目。

代码实现

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        ##感觉这个思路十分新
        n=len(nums)
        tempcount=[]
        for i in range(n+2):
            tempcount.append(0)
        for i in range(n):
            if nums[i]>0 and nums[i]<=n:
                tempcount[nums[i]]+=1
        for i in range(1,n+2):
            if tempcount[i]==0:
                return i