41. The first missing positive number

Hash table method ( Space n)

New array method （ Space time n）

class Solution {
    
    public int firstMissingPositive(int[] nums) {
    
        int len=nums.length;
        // First construct a temporary array  tmp
        int[] temp=new int[len];
        int j;
        for(int i=0;i<len;i++){
    
            if(nums[i]>0&&nums[i]<=len){
    
                // hold  A[i]  Copied to the  tmp[A[i]-1]  The location of 
                temp[nums[i]-1]=nums[i];
            }
        }
        // And then from the position  0  Start checking  tmp, If you find that the value of this position does not match the index number , It means that the missing number is found 
        for(int i=0;i<len;i++){
    
            if(temp[i]!=i+1){
    
                return i+1;
            }
        }
        return len+1;

    }
}

Exchange position method （ Space 1 Time n）

class Solution {
    
    public int firstMissingPositive(int[] nums) {
    
        int len=nums.length;
        for(int i=0;i<len;i++){
    
            //nums[i] =4  Follow  num[3] in 
            if(nums[i] > 0 &&nums[i]<len&&nums[i]!=nums[nums[i]-1]){
    
                int temp=nums[i];
                nums[i]=nums[nums[i]-1];
                nums[nums[i]-1]=temp;
            }
        }
        for(int i=0;i<len;i++){
    
            //nums[0] 1 ;0+1 1
            if(nums[i]!=i+1){
    
                //return Yes. i+1  If nums[i=1] 3 ;  You should go back to 3
                return i+1;
            }
        }
        //  All meet   So the smallest thing that doesn't appear is len+1 {1,,2,3} return 4
        return len+1;
    }
}

Change the array method

class Solution {
    
    public int firstMissingPositive(int[] nums) {
    
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
    
            if (nums[i] <= 0) {
    
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
    
            int num = Math.abs(nums[i]);
            if (num <= n) {
    
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
    
            if (nums[i] > 0) {
    
                return i + 1;
            }
        }
        return n + 1;
    }
}