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.
分析：
因为数组的大小为n，因此那个缺失的整数只可能的范围[1,n+1]
方法一：需要O(n)的空间，设置一个数组vis用来标记该下标对应的数字是否出现过。
int firstMissingPositive(int* nums, int numsSize) {
int vis[10000];
int i;
for(i=1;i<=numsSize;i++){
vis[i]=0;
}
for(i=0;i<numsSize;i++){
if(nums[i]>0&&nums[i]<=numsSize){
vis[nums[i]]=1;
}
}
for(i=1;i<=numsSize;i++){
if(vis[i]==0){
return i;
}
}
return numsSize+1;
}
方法二：将数组中值在1~n的数组元素放到对应下标为该值减1的地方。例如: A[3]=2，则将A[2-1]与A[3]进行交换。最后遍历数组直到元素值不等于下标值加一，则该下标加一 就是第一个缺失的正整数
int firstMissingPositive(int* nums, int numsSize) {
int i,t;
for(i=0;i<numsSize;i++){
while(nums[i]!=(i+1)&&nums[i]>0&&nums[i]<=numsSize){
//保证每个元素回到适当的位置
if(nums[nums[i]-1]==nums[i]){
break;
}
t=nums[nums[i]-1];
nums[nums[i]-1]=nums[i];
nums[i]=t;
}
}
for(i=0;i<numsSize;i++){
if(nums[i]!=(i+1)){
return i+1;
}
}
return numsSize+1;
}