[LintCode]失われた最初の正の整数

 1 class Solution {
 2 public:
 3     /**    
 4      * @param A: a vector of integers
 5      * @return: an integer
 6      */
 7     int firstMissingPositive(vector<int> A) {
 8         // write your code here
 9         int n = A.size();
10         for (int i = 0; i < n; i++)
11             while (A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
12                 swap(A[i], A[A[i] - 1]);
13         for (int i = 0; i < n; i++)
14             if (A[i] != i + 1)
15                 return i + 1;
16         return n + 1;
17     }
18 };