41.|41. First Missing Positive 41.FirstMissingPositive

文章图片
image.png 【41.|41. First Missing Positive】因为数组内部本身可能就有负数，所以不能把index为a[i]的遍历变成负数来标记这个index是不是存在
但是可以swap，在index为i的位置，一定是跟index为a[i]-1的数交换，有2中情况停止交换

index为a[i]-1的数就是i
a[i]不是正数，这时候也没法交换

class Solution(object): def firstMissingPositive(self, a): """ :type nums: List[int] :rtype: int """ for i in range(len(a)): if a[i]==i+1: continue while 1<=a[i]<=len(a) and a[a[i]-1]!=a[i]: t = a[i]-1 a[i], a[t] = a[t], a[i] for i in range(len(a)): if a[i]!=i+1: return i+1 return len(a)+1s=Solution() print(s.firstMissingPositive([3,4,-1,1]))