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,2,0]缺少3，[3,4,-1,1]缺少2。
【思路】
1. 复杂度为O(n2)
在数组中分别查找1，2，3，···，nums.length，返回查找到的第一个不在数组中的值。最坏情况下需要nums.length次遍历数组，平均时间复杂度为O(n2)。
2. 复杂度为O(n)
如何更加简单得处理这个问题呢？在使用固定空间的约束下，我们当然是要在原来的数组上做文章。想法如下：
（1）遍历数组，如果当前元素nums[i]等于i+1，则表示第i+1个正数没有缺失，继续向后遍历；
（2）如果当前元素小于等于零或者大于nums.length，则继续向后遍历；
（3）如果当前元素大于零而且小于等于nums.length，则把nums[nums[i]-1]与nums[i]交换。
这样处理的结果就是我们把每一个正数n都放在了n-1的位置上，然后再从头遍历数组，如果某个位置k不满足nums[k] == k+1，则返回缺失的正数k+1，如果遍历到数组末尾，则返回nums.length+1；
【java代码】
public class Solution {
public int firstMissingPositive(int[] nums) {
if(nums == null || nums.length == 0) return 1;
int i = 0;
while(i < nums.length){
if(nums[i] == i+1) i++;
else if(nums[i] > 0 && nums[i] <= nums.length){
int temp = nums[nums[i] - 1];
if(temp != nums[i]){
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
else i++;
}
else i++;
}
for(i = 0; i < nums.length; i++)
if(nums[i] != i+1) return i+1;
return nums.length+1;
}
}