Title:
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放到数组中0的位置，2放到1的位置...
int firstMissingPositive(int A[], int n) { for (int i = 0 ; i < n ; i++){ while ( A[i] != i+1){ if (A[i] >= n || A[i] <= 0 || A[i] == A[A[i-1]])// A[i] == A[A[i]-1]判断的是如果这两个元素本身相等，就不用交换，不然会陷入死循环 break; //交换A[i] 和 A[A[i]-1] int t = A[i]; A[i] = A[t-1]; A[t-1] = t; } } for (int i = 0 ; i < n ; i++){ if (A[i] != i+1) return i+1; } return n+1; }
LeetCode: first Missing Positive
原文：http://www.cnblogs.com/yxzfscg/p/4449661.html