缺失的第一个正数(力扣100)

最朴素的想法就是从1开始查找看看谁不在时间复杂度为On但是需要把原数组变成集合空间复杂度为On不符合题目的常数级空间开销我们要找的是“第一个缺失的正数”。如果数组长度是 $N$那么这个答案一定落在[1, N1]这个区间里。既然答案在1到 $N$ 之间我们就定一个规矩——数字1必须坐在索引0的位置上数字2必须坐在索引1的位置上数字x必须坐在索引x-1的位置上遍历一遍数组。看到一个数字如果它不在自己的座位上就跟对应座位上的数字交换一直换到每个数字都坐在了自己的座位上。排好座之后再检查一遍数组。第一个座位号和数字对不上的地方就是答案。实现如下class Solution(object): def firstMissingPositive(self, nums): :type nums: List[int] :rtype: int nlen(nums) for i in range(n): while 0nums[i]n and nums[nums[i]-1]!nums[i]: jnums[i]-1 nums[i],nums[j]nums[j],nums[i] for i in range(n): if nums[i]!i1: return i1 return n1需要注意的是不是交换完一次就完事了还要继续判断是否需要继续换因为交换之后的数字可能依然是一个遍历过的位置的合法数字