First Missing Positive(Bucket Sort)

问题：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.

解题思路： 用类似于桶排序的算法，考虑第一个缺少的数包括0和正整数的场景：这种情况下排序后第i个元素应该等于i：

• A[i]==i
• A[i]==A[A[i]]

由于这个问题只考虑正整数，因而要左移一位，第i个元素应该等于i+1

public int firstMissingPositive(int[] A) {
        int n = A.length;

        for (int i = 0; i < n; i++) {
            while (A[i] != i + 1) {
                if (A[i] <= 0 || A[i] >= n)
                    break;

                if(A[i]==A[A[i]-1])
                    break;

                int temp = A[i];
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }

        for (int i = 0; i < n; i++){
            if (A[i] != i + 1){
                return i + 1;
            }
        }

        return n + 1;
    }

References:

1 LeetCode – First Missing Positive (Java)