41. 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.

technical speaking, it is a hash table question. but the hash key here is the array index. put the corresponding number in their niche. then swipe the array from the beginning, first not match is what we need,

public class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i=0; i< nums.length; i++){
           if( nums[i] != i+1 && nums[i] > 0 && nums[i] <=nums.length && nums[i] != nums[nums[i]-1]){
               int t = nums[nums[i] -1]; // cache this number first, other wise won't work.
               nums[nums[i] -1] = nums[i];
               nums[i] = t;
               i--;
           }
        }

        for(int i=0; i< nums.length;i++){
            if(nums[i] != i+1) return i+1;
        }
        return nums.length+1;
    }
}