First Missing Positive @LeetCode

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.

	package leetcode;
	import java.util.Arrays;
	/**
	* Solution: Sort. Move number to index and make them have a map relation. It's easy to find the missing one.
	* Like A[0] = 1. The first element is 1. go next and so on..
	* At first, I was confused by some cases. After carefully thinking, it doesn't matter.
	* Like [3,-4,-1,1] after swap, A will be [1,4,3,-1]. if 2 exists, it must be in index 1, so is 2.
	* Generally, we swap A[A[i] - 1], A[i], if duplicate, we stop swapping.
	*
	* Test case:
	* In my view,this problem isn't good, it only works for some specific cases around 1,2.
	* int[] A = {-1,3,4,5}; --> 1 int[] A = {6,7,8,9} -->1. These cases can't be used.
	*
	* Reference: http://fisherlei.blogspot.com/2012/12/leetcode-first-missing-positive.html
	* @author jeffwan
	* @date Apr 2, 2014
	*/
	public class FirstMissingPositive {
	public static void main(String[] args) {
	int[] A = {3, 4, -1 ,1};
	System.out.println(firstMissingPositive(A));
	}
	public static int firstMissingPositive(int[] A) {
	if (A == null) {
	return 1;
	}
	for (int i = 0; i < A.length; i++) {
	while (A[i] > 0 && A[i] < A.length && A[i] != i + 1) {
	int temp = A[A[i] - 1];
	if (temp == A[i]) {
	break;
	}
	A[A[i] - 1] = A[i];
	A[i] = temp;
	}
	}
	for (int i = 0; i < A.length; i++) {
	if (A[i] != i + 1) {
	return i + 1;
	}
	}
	return A.length + 1;
	}
	}

view raw FirstMissingPositive.java hosted with ❤ by GitHub