leetcode_41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：

输入：nums = [3,4,-1,1]
输出：2
示例 3：

输入：nums = [7,8,9,11,12]
输出：1
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n=len(nums)
        #如果1不在列表中，最小正数是1
        if 1 not in nums:
            return 1
        #所有0或负数全变为1
        for i in range(n):
            if nums[i]<=0:
                nums[i]=1
        #将值对应的位置的值做标记（变为负数）
        for x in nums:
            if abs(x)<=n:
                nums[abs(x)-1]=-abs(nums[abs(x)-1])
        
        for i in range(n):
            if nums[i]>0:#大于0 表示没有做标记，说明该数不存在
                return i+1
        
        return n+1