[Leetcode] 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.

使用桶排序的思想，用A[i]去装i+1，拍好序之后寻找第一个和自己标号不对应的“桶”的位置。

    public int firstMissingPositive(int[] A) {
        for(int i = 0; i < A.length; i++) {
            int num = A[i], temp;
            while(num > 0 && num <= A.length && A[num-1] != num) {
                temp = A[num-1];
                A[num-1] = num;
                num = temp;
            }
        }
        for(int i = 0; i < A.length; i++) {
            if(A[i]-1 != i)
                return i+1;
        }
        return A.length + 1 ;
    }