题目
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.
分析
给定一个乱序的数组，找出第一个缺失的整数。但是算法要求时间为O(n)，空间为常量。因此不能使用排序，快排也需要O(n*log(n))，我使用的方法是找一个数组保存出现的正数，然后再搜索数组中最小的未出现的正数。
其他别人好的算法是：将出现的正数和那个位置上的数字进行交换，之后再依次寻找未出现的正数，这样就不需要数组，节省了内存。
int firstMissingPositive(int* nums, int numsSize) {
int a[1000000]={0};
for(int i=0;i<numsSize;i++)
{
if(nums[i]>0)
a[nums[i]]=1;
}
for(int i=1;i<1000000;i++)
{
if(a[i]==0)
return i;
}
return 1;
}
