思路分析
本质上这个问题是在考察计数排序，我们可以简单来分析一下。计数排序的思想是，将某个数字放到数组中对应的位置上，然后从前往后遍历数组，如果有元素就直接输出，这样就得到了一个有效的升序序列。对于这个问题，由于它给定的数字有范围，我们同样可以尽量将某个元素放到它所应该在的地方，这样，从前往后遍历，哪个地方如果是空位，说明这里就是缺失的正数。
题目中给定的是n个元素，这样，对于小于等于零以及大于n的元素，我们就认为它是空位，不予考虑。然后我们从前向后遍历，找到当前第i个元素不在它应该在的位置上的话，就把它交换到它应该在的位置上面去。如果这样只交换一次的话，第i个位置上的元素可能还是不合法，所以要用while循环交换多次，直到彻底无法交换，即达到了终止条件A[i] == A[A[i]]。最后，我们就得到了一个尽量合法的序列，其中每一个1~n范围内的元素都尽量在它应该在的位置上面，从而可以轻易找出缺失的正整数。注意这个题目中，由于有效范围是正数，因此我们应该把映射错位一下，应该有：A[i] = i + 1。
代码
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)
class Solution {
public:
int firstMissingPositive(int A[], int n) {
rep(i, n) {
while ( i + 1 != A[i] ) {
if ( A[i] < 1 || A[i] > n || A[i] == A[A[i] - 1] ) break;
swap(A[i], A[A[i] - 1]);
}
}
rep(i, n) if ( A[i] != i + 1 ) return i + 1;
return n + 1;
}
};