First Missing Positive

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.

Solution: Counting sort

Counting sort - Wikipedia

跟Counting sort一样，利用数组的index来作为数字本身的索引，把正数按照递增顺序依次放到数组中。即让A[0]=1, A[1]=2, A[2]=3, ... ,如果哪个数组元素违反了A[i]=i+1即说明i+1就是我们要求的第一个缺失的正数。

对于不在范围内的数字，直接跳过，比如说负数，0，或者超过数组长度的正数, 或者当前的数字所对应的下标已经是对应数字。

扫描数组两遍，时间复杂度是O(2*n)=O(n)，而且利用数组本身空间，只需要一个额外变量，所以空间复杂度是O(1)。

public class Solution {
    public int firstMissingPositive(int[] A) {
        if(A == null || A.length == 0)
            return 1;
        
        for(int i = 0; i < A.length; i++) {
            // 如果A[i]超出范围，负数或0，下标和值对应，都跳过
            if(A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) {
                int temp = A[A[i] - 1];
                A[A[i] - 1] = A[i];
                A[i] = temp;
                i--;
            }
        }
        
        for(int i = 0; i < A.length; i++) {
            if(A[i] != i + 1) {
                return i + 1;
            }
        }
        return A.length + 1;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/20884585