[Leetcode] First Missing Integer

Problem 

Given an unsorted integer array, find the first missing positive integer.
For example,
Input [1,2,0] return 3,
Input [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

Algorithm

The first missing positive integer must lies in 1 to A.length+1. 

If O(n) is allowed, we can use a BitSet or a boolean array to register the occurrence of each number in the range [0, A.length] (ignore all numbers out of this range). After registration, the first missing positive integer can be found. 

If constant space is required. We can move all numbers to their "magic position", i.e. A[i] = i+1, ignoring numbers out of range. For example, [4,3,2,1] should be [1,2,3,4].

Code