Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
题意分析：
本题是给一个整数的数组，让你按顺序找出第一个缺失的正整数。也就是说从1开始查找，找到了1再找2，这样一直找到缺失的第一个正整数。比如[1,2,0] return 3,[3,4,-1,1] return 2. 要求时间复杂度O(n) ，空间复杂度为常数。
解答：
我们要注意到这样一个事实，数组的下标是有标记意义的。所以我们可以把数字放到相应的下标下面，这样理想情况下所有的正数都能一一对应到0~N-1的下标中，这里面可以使用交换来实现。这样一次循环之后，正整数i应该交换到了i-1下标对应的元素中。然后在进行一次循环查找第一个不符合的元素输出即可。
AC代码：
class Solution(object):
def firstMissingPositive(self, nums):
i, n = 0, len(nums)
while i < n:
if nums[i] > 0 and nums[i] <= n and nums[i] != nums[nums[i] - 1]:
# swap
temp = nums[i]
nums[i] = nums[nums[i] - 1]
nums[temp - 1] = temp
else:
i += 1
for i, v in enumerate(nums):
if v != i + 1:
return i + 1
return n + 1