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（未排序）中第一个缺少的正整数。要求O(n)时间复杂度。
这道题的直接思路就是先排序，然后遍历一遍就能找到第一个缺少的正整数了。不过这样的话，时间复杂度是O(nlogn)。
题目要求O(n)时间复杂度，那么还能不能更快些呢？可以考虑从排序上动手脚。类似于计数排序的思路，申请个同样大小的空数组B，然后给定数组A，把A中出现的数字放到B中对应于B下标的位置（如果该数字大小超过B的范围，则不处理），例如把5放到B[4]里等等。最后，再遍历B数组，就能找到第一个缺少的正整数了。
由于上面申请的B数组和A一样大，那么可不可以直接用A来代替B呢？当然可以，就是在遍历A的时候，如果数字和位置不对应，就交换到对应位置即可。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution
{
public:
int firstMissingPositive(int A[], int n)
{
for(int i = 0; i < n; ++ i)
while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
swap(A[i], A[A[i] - 1]);
for(int i = 0; i < n; ++ i)
if(A[i] != i + 1)
return i + 1;
return n + 1;
}
};