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.
找到第一个消失的正整数。而且复杂度是O（n）
思路：排序，然后就很简单了。
但是怎么在O（n）的复杂里面排序呢。
要结合题目的特点，A[i]需要等于A[A[i] - 1]，只要有不相等的就交换。
比如A[i]等于5，而如果要连续的正整数，5必须出现在A[A[i] - 1]也就是A[5-1]上。
最后排序而成的A就像[1,2,3,4,5,6,8,-4,6]这样。
很容易找出第一个消失的正整数是7
代码如下
public class FirstMissingPositive {public static void main(String[] args) {int[] A = new int[]{};System.out.println("firstMissingPositive: " + firstMissingPositive(A));}public static int firstMissingPositive(int[] A) {for (int i = 0; i < A.length; ) {if (A[i] == i + 1 || A[i] <= 0 || A[i] > A.length) {i++;} else if (A[A[i] - 1] != A[i]) {swap(A, A[i] - 1, i);} else {i++;}} int i = 0;while ( i < A.length) {if (A[i] != i + 1) {return i + 1;}i++;}return i + 1;}private static void swap(int[] A, int i, int j){int temp = A[i];A[i] = A[j];A[j] = temp;}
}