题目描述:
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.
首先未出现的数的范围必是在[1,N],所以可以用一个N长的数组来做标记,但是这样是O(N)的空间,在网上看有大牛提出了利用原数组来做标记的办法,首先因为原来包含的0和负数都不会出现在[1,N]中,即对结果是没有贡献的,所以可以在预处理阶段将这些数置为一个很大的正数,然后扫描数组,遇到一个数A[I],得到它原来表示的那个数(负数取正),然后将它表示的位置的数置反(A[ A[I] ] *=-1 ),最后扫描数组第一个遇到的正数即该位置未出现过。
int firstMissingPositive(int A[],int n) { if (!A||n<=0) return 1; const int INVALID= 10000000; int i=0; for(i=0;i<n;i++) if (A[i]<=0) A[i]=INVALID; for(i=0;i<n;i++) { int tmp=A[i]>0?A[i]:-A[i]; if (tmp<=n) { if (A[tmp-1]>00) A[tmp-1]*=-1; } } int ans=n+1; for(i=0;i<n;i++) if( A[i]>0) { ans=i+1; break; } return ans; }