Given an unsorted integer array, find the first missing positive integer.
For example,Given[1,2,0]
return3
,and[3,4,-1,1]
return2.
Your algorithm should run in O(n) time and uses constant space.
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++)
{
if(nums[i]>0&&nums[i]<=n)
{
if(nums[i]-1!=i&&nums[nums[i]-1]!=nums[i])
{
int temp = nums[nums[i]-1]; //此处要注意交换顺序！！！千万不要在交换的过程中改变变量的值
nums[nums[i]-1] = nums[i];
nums[i] = temp;
i--;
}
}
}
for(int i=0;i<n;i++)
{
if(nums[i]!=i+1)
return i+1;
}
return n+1;
}
}
