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.
解题思路一：
刚看到题目的时候感觉无从下手，后来仔细理解题意，需要找到first missing positive integer，这个数肯定是1---nums.length+1的一个值，因此我们可以开一个布尔数组，存储i是否存在，JAVA实现如下:
public int firstMissingPositive(int[] nums) {
boolean[] num=new boolean[nums.length];
for (int i = 0; i < nums.length; i++)
if (nums[i] > 0&&nums[i] <= nums.length)
num[nums[i]-1] = true;
for (int i = 0; i < num.length; i++)
if (!num[i])
return i+1;
return nums.length+1;
}
解题思路二：使用bool数组会有O(N)的空间复杂度，直接采用交换的方法可以避免，JAVA实现如下：
static public int firstMissingPositive(int[] nums) {
if(nums.length==0)
return 1;
for (int i = 0; i < nums.length; ) {
if (nums[i] >= 0 &&nums[i] < nums.length &&nums[i] != i && nums[i] != nums[nums[i]]){
int temp=nums[i];
nums[i]=nums[nums[i]];
nums[temp]=temp;
}
else i++;
}
for (int i = 1; i < nums.length; ++i)
if (nums[i] != i)
return i;
return nums[0] == nums.length ? nums.length + 1 : nums.length;
}