41. First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given[1,2,0]return3,
and[3,4,-1,1]return2.

Your algorithm should run inO(n) time and uses constant space.

思路：假设A[0]=1, A[1]=2 ...排好，那么就可以查地方了

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

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

        return nums.length+1;
    }

    public void swap(int[] A,int i,int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}