Java日记2018-08-09

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.

把1放在数组第一个位置nums[0]，2放在第二个位置nums[1]，即需要把nums[i]放在nums[nums[i] - 1]上，那么我们遍历整个数组，如果 nums[i]为整数且不大于n，另外nums[i]不等于nums[nums[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，代码如下：

public static int findFirPos(int[] arr){
        if(arr==null || arr.length==0) return -1;
        int len = arr.length;
        int i=0;
        while (i < len){
            //注意要把arr[i]>0最先判断，因为有可能arr[i]是负数导致arr[arr[i]-1]越界
            if(arr[i]>0 && arr[i]<=len && arr[i]!=arr[arr[i]-1] ){
                swap(arr,i,arr[i]-1);
            } else {
                i++;
            }
        }
        
        for(i=0;i<len;i++){
            if(arr[i]!=i+1){
                System.out.println(i+1);
                return i+1;
            }
        }
        System.out.println(len+1);
        return len+1;
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }