1. First Missing Positive
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.
桶排序，只不过不许用额外空间。所以，每次当A[i]!= i+1的时候，将A[i]与A[A[i]]交换，直到无法交换位置。终止条件是 A[i]== A[A[i]] 或者 A[i]为负，A[i]>n。然后i -> 0 到n走一遍就好了。
int firstMissingPositive(int A[], int n) {int i=0;while(i<n){if(A[i]!=i+1 && A[i]>=1 &&A[i]<=n && A[A[i]-1] !=A[i])swap(A[i],A[A[i]-1]);elsei++;}for(int i=0; i<n;i++){if(A[i]!=i+1)return i+1;}return n+1;
}2.
未完待续