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.

 1 class Solution {
 2 public:
 3     int firstMissingPositive(int A[], int n) {
 4         int i = 0;
 5         while(i < n) {
 6             if(A[i] != i+1 && A[i] >= 1 && A[i] <= n && A[i] != A[A[i]-1]) {
 7                 swap(A[i], A[A[i]-1]);
 8             }
 9             else i++;
10         }
11         for(int i = 0; i < n; i++) {
12             if(A[i] != i+1) return i+1;
13         }
14         return n+1;
15     }
16 };

First Missing Positive,布布扣,bubuko.com

First Missing Positive

原文：http://www.cnblogs.com/zhengjiankang/p/3646805.html