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.
方法比较巧，先把所有元素的值-1，重新组织元素使A[i] = i，这样只要找到第一个A[i] != i 的 i。注意要用while循环，for循环的continue是从下一次循环开始的。
1 class Solution { 2 public: 3 int firstMissingPositive(int A[], int n) { 4 int tmp; 5 for (int i = 0; i < n; ++i) { 6 A[i]--; 7 } 8 int i = 0; 9 while (i < n) { 10 if (A[i] != i && A[i] >= 0 && A[i] < n && A[i] != A[A[i]]) { 11 tmp = A[i]; 12 A[i] = A[A[i]]; 13 A[tmp] = tmp; 14 } else { 15 i++; 16 } 17 } 18 for (int i = 0; i < n; ++i) { 19 if (A[i] != i) { 20 return i + 1; 21 } 22 } 23 return n + 1; 24 } 25 };
[Leetcode] First Missing Positive,布布扣,bubuko.com
[Leetcode] First Missing Positive
原文：http://www.cnblogs.com/easonliu/p/3630599.html