题解 | #缺失的第一个正整数#

方法一：时间复杂度o(n),空间复杂度o(n)

import java.util.*;


public class Solution {
    /*
    * 如果数组中所有数都为1-n范围内，且1-n全部都在，为n+1
    * 如果有一个不在1-n范围内，则结果<=n
    * 依据这样的思路可以想到：遍历数组，如果不在1-n范围内，肯定不是要求的数字，删除
    * 如果在1-n范围内，将对应的hash表值设置为true，从前往后枚举hash表找到第一个false的值
    *
    * */
    public int minNumberDisappeared(int[] nums) {
        HashMap<Integer, Boolean> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 1 && nums[i] <= nums.length) {
                hashMap.put(nums[i], true);
            }
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!hashMap.containsKey(i))
                return i;
        }
        return nums.length + 1;
    }
}

方法二：原地hash，空间复杂度o(1),时间复杂度o(n)

public int minNumberDisappeared(int[] nums) {
        int n = nums.length;
        //将所有的负数置为n+1，下面负数不参与讨论
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            //将在n范围内的值对应下标的值置为负值，说明，该下标的值出现过
            if (Math.abs(nums[i]) <= n) {
                nums[Math.abs(nums[i]) - 1] = -1 * Math.abs(nums[Math.abs(nums[i]) - 1]);
            }
        }
        //第一个正数说明是未出现的值
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }