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.

 

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
        	if (nums[left] == left + 1) {
        		left++;
        	} else if (nums[left] <= left || nums[left] > right || nums[left] == nums[nums[left]-1]) {
        		nums[left] = nums[--right];
        	} else {
        		swap(nums, left, nums[left]-1);
        	}
        }
        return left + 1;
    }

	private void swap(int[] nums, int i, int j) {
		// TODO Auto-generated method stub
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
}