Given an unsorted integer array, find the first missing positive integer.

For example,
Given[1,2,0]return3,
and[3,4,-1,1]return2.

Your algorithm should run in O(n) time and uses constant space.

https://oj.leetcode.com/problems/first-missing-positive/

思路：交换数组元素，使得数组中第i位存放数值(i+1)。最后遍历数组，寻找第一个不符合此要求的元素，返回其下标。整个过程需要遍历两次数组，复杂度为O(n)。

public class Solution {	public int firstMissingPositive(int[] A) {		if (A == null && A.length == 0)			return 1;		int n = A.length;		int i;		for (i = 0; i < n; i++) {			while (A[i] > 0 && A[i] != i + 1 && A[i] <= n					&& A[i] != A[A[i] - 1]) {				swap(A, i, A[i] - 1);			}		}		for (i = 0; i < n; i++)			if (A[i] != i + 1)				return i + 1;		return n + 1;	}	private void swap(int[] a, int i, int j) {		int tmp = a[i];		a[i] = a[j];		a[j] = tmp;	}	public static void main(String[] args) {		 System.out.println(new Solution().firstMissingPositive(new int[] { 1,		 2, 0 }));		 System.out.println(new Solution().firstMissingPositive(new int[] { 3,		 4, -1, 1 }));		 System.out		 .println(new Solution().firstMissingPositive(new int[] { 0 }));		 System.out		 .println(new Solution().firstMissingPositive(new int[] { 1 }));		 System.out		 .println(new Solution().firstMissingPositive(new int[] { 2 }));				 System.out.println(new Solution()		 .firstMissingPositive(new int[] { 0, 1 }));		System.out.println(new Solution()				.firstMissingPositive(new int[] { 1, 1 }));	}}