41. 缺失的第一个正数

哈希表法(空间n)

新建数组法（空间时间n）

class Solution {
    
    public int firstMissingPositive(int[] nums) {
    
        int len=nums.length;
        //先构造一个临时数组 tmp
        int[] temp=new int[len];
        int j;
        for(int i=0;i<len;i++){
    
            if(nums[i]>0&&nums[i]<=len){
    
                //把 A[i] 复制到 tmp[A[i]-1] 的位置
                temp[nums[i]-1]=nums[i];
            }
        }
        //然后从位置 0 开始检查 tmp，如果发现该位置的值和索引号不匹配，就说明找到了缺失的数了
        for(int i=0;i<len;i++){
    
            if(temp[i]!=i+1){
    
                return i+1;
            }
        }
        return len+1;

    }
}

交换位置法（空间1 时间n）

class Solution {
    
    public int firstMissingPositive(int[] nums) {
    
        int len=nums.length;
        for(int i=0;i<len;i++){
    
            //nums[i] =4 跟 num[3]换
            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的是i+1 如果nums[i=1] 3 ； 则应该返回3
                return i+1;
            }
        }
        // 所有的都符合 那么最小的没有出现的就是len+1 {1,，2,3}返回4
        return len+1;
    }
}

改变数组法

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;
    }
}