First Missing Positive

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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.
Solution: Although we can only use constant space, we can still exchange elements within input A.
Swap elements in A and try to make all the elements in A satisfy: A[i] == i + 1. Pick out the first one that does not satisfy A[i] == i + 1.

代码：

 class Solution {  
 public:  
   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]);          
       } else {  
         i++;          
       }  
     }  
     for (i = 0; i < n; ++i) {  
       if (A[i] != (i + 1)) {  
         return i + 1;                
       }  
     }  
     return n + 1;  
   }  
 };