缺失的第一个正数

---

image.png

例：将1-100映射到nums[0-99]，超出的不用管，思路参考 剑指 Offer 03. 数组中重复的数字，为什么0要映射1？因为映射0的话会很麻烦，[0,1]的情况下解是2，[1]的情况下解也是2，自己体会。

最后将所有值n归位到对应nums[n-1]，从0位扫到到n-1位，发现nums[i]!=i+1就跳出，i+1就是解。如果最优值是初始值-1，那么确实的第一个正数就是大于[1,len(nums)]的第一个数。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if len(nums)==0:
            return 1
        for i in range(len(nums)):
            if (nums[i]!=i+1):
                n=nums[i]
                while(n-1>=0 and n-1<len(nums) and n!=nums[n-1]):
                    t=nums[n-1]
                    nums[n-1]=n
                    n=t
        res=-1
        for i in range(len(nums)):
            if(i+1!=nums[i]):
                res=i+1
                break
        if res==-1:
            return len(nums)+1
        else:
            return res