题解 | #缺失的第一个正整数#

这个题目还是有点复杂的，主要在于时间复杂度要求O(n)，空间复杂度要求O(1)。因此常规的思路都不行，最后还是看了题解才知道咋做。

1. 首先要明白缺失第一个正整数要么是1-n，要么是n+1，其中n是nums数组的长度。这是很容易理解的，因为当nums数组里存放的就是1-n，那么最小正整数就是n+1，如果数组中有大于等于1个元素不在范围1-n中，则缺失的最小正整数就是1-n之间的某个值。
2. 遍历该数组，如果nums[i]元素是在1-n范围间的话，就存在数组的nums[i]下标处。也就是令nums[nums[i]]=nums[i]，当然这样操作时要把原来nums[nums[i]]中的元素放到nums[i]的位置去。如此遍历一遍就整理好数组了。有一个小技巧就是把nums扩容一个元素，这样下标和num[i]的值就可以直接对应了。
3. 整理好数组后遍历一遍，如果nums[i]是在1-n范围内的就遍历下一个，否则直接返回下标i即可，如果nums数组整理后第1-n个元素刚好是1-n，则返回n+1.

代码如下：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums) -> int:
        # write code here
        nums.append(-1)  # 将nuns数组扩充到长度n+1
        i = 0 
        while i <= len(nums)-1:
            if nums[i]>=1 and nums[i] <= len(nums)-1:
                a , b = nums[nums[i]] , nums[i]
                nums[nums[i]] = b
                nums[i] = a
                if i == nums[i]:
                    i+=1
            else:
                i+=1
        for i in range(1,len(nums)):
            if nums[i]<1 or nums[i]>=len(nums):
                return i
        return len(nums)

nums=[1,0,2]
print(Solution().minNumberDisappeared(nums))