41. First Missing Positive（找到数组中未出现的最小正整数）

Total Accepted: 87074 Total Submissions: 348588 Difficulty: Hard Contributors: Admin 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.

方法： 遍历一遍，把正确合法的正整数方在正确的位置上即可。比如我们找到元素5，就把5换到A[4]上，因为数组从0下标开始。最终结果数组A[i] != i+1 的就是该位置上的正整数没有出现过，返回i+1即可。

代码如下：

class Solution(object): def firstMissingPositive(self, nums): n = len(nums) for i in range(0, n): while nums[i] > 0 and nums[i] <= n and nums[nums[i]-1] != nums[i]: nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] for i in range(0, n): if nums[i] != i+1: return i+1 return n+1

呵呵，人生苦短，我用Python。