要找出一个数组nums中缺失的第一个正整数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

题目链接

采用原地Hash的思想。

因为Hash可以做到时间复杂度是N，但是做不到空间复杂度也是N，所以需要把空间复杂度从N降成1，就是说不能再要一个额外的数组空间。

可以在原来的nums数组上做文章。

数组长度为N，那么缺失的第一个正整数就是在1-N+1的范围之内，我们先把数组中所有的非正整数转换成N+1，再利用负数来标记已经出现过的数字，最后只需要找没有负数的下标就可以了。

代码如下：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        N=len(nums)#整个数组的长度
        for index in range(0,N):#这里需要注意只能通过下标来改变数组里面的内容
            if nums[index]<=0:#如果是非正整数
                nums[index]=N+1#值修改为N+1
        for num in nums:
            if abs(num)>N:continue#如果值大于等于N+1，那么不进行标记，因为也标记不了，但是有答案限制
            else:#如果数字对应的下标没有被标记成为负数，则把数字对应的下标标记成为负数（1-N依次对应下标0-N-1）
                if nums[abs(num)-1]>0:nums[abs(num)-1]=-nums[abs(num)-1]
        for index in range(0,N):
            if nums[index]>0:return index+1#如果下标为正整数则没有被标记，返回
        return N+1#否则答案就是N+1