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.

难度：hard

Solution: Bucket Sort

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

这个问题可以推广到[m, n]区间内第一个缺失的元素，同样利用数组index和这些数的一一对应关系。