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)时间和常数空间。肯定不能使用基于比较的排序，于是考虑counting sort，Bucket sort，radix sort等O（n）的Distribution sorts 排序算法。借助桶排序的思想，我们重用输入的数组，进行数据交换使得A[0]=1,A[1]=2,...A[i]=i+1，这样我们就可以从前向后扫描，如果那个数违反了A[i]=i+1，那就是说明第一个缺失的正数是i+1。所以可以扫描数组，把数A[i]换到index为A[i]-1处，但是对于负数，0或者不在数组range内的数跳过。有一个比较tricky的地方是，当进行交换后，要注意换过来的新数是否满足A[i]=i+1，如果不满足还要继续进行交换。所以我们有i--的操作，交换后仍然检查一次当前位置。最后在wiki上摘录排序算法分类如下：

Sorting algorithms
Exchange sorts
Bubble sort Cocktail sort Odd–even sort Comb sort Gnome sort Quicksort Stooge sort Bogosort
Selection sorts
Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort
Insertion sorts
Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts
Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort Strand sort
Distribution sorts
American flag sort Bead sort Bucket sort Burstsort Counting sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts
Bitonic sorter Batcher odd–even mergesort Pairwise sorting network
Hybrid sorts
Block sort Timsort Introsort Spreadsort JSort
Other
Topological sorting Pancake sorting Spaghetti sort

AC Code

public class Solution {
    public int firstMissingPositive(int[] A) {
        int n = A.length;
        if(n == 0) return 1;
        
        for(int i = 0; i < n; i++){//
            if(A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1] ){
                swap(A, i, A[i]-1);
                i--;
            }
        }
        
        for(int i = 0; i < n; i++){
            if(A[i] != i+1){
                return i+1;
            }
        }
        return n + 1;
    }
    
    void swap(int [] A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}