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
     
      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
     
      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