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

First Missing Positive.java

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A.length == 0) return 1;
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= A.length && A[i] > 0 && A[i] != i+1) {
                if (A[A[i]-1] != A[i]) {
                    int tmp = A[A[i]-1];
                    A[A[i]-1] = A[i];
                    A[i] = tmp;
                    i--;
                }
            }           
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i+1) return i+1;
        }
        return A.length+1;
    }
}

很巧妙的一个答案。
比自己的想法好很多然后就贴过来了。

自己的想法：
一个HashMap维护（但是要额外的空间）
尽管是O(n)的但是空间也是....