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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        // 算法核心思想：通过按正整数顺序的方式创建哈希记录，遍历数组登记哈希，然后遍历哈希
        // 算法时间复杂度O(N)，额外空间复杂度O(N)（没做到O(1)）

        // 1.遍历数组，记录数组中出现过的最小正整数值，并将所有正整数记录哈希表
        // 记录最小值是为了简化判断，若最小值>1可以直接返回1
        int min = Integer.MAX_VALUE;
        HashMap<Integer, Boolean> hm = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                hm.put(nums[i], true);
                if (nums[i] < min) {
                    min = nums[i];
                }
            }
        }
        if (min > 1) {
            // 若数组中出现过的最小正整数比1大，则可直接输出最小正整数1
            return 1;
        }
        // 其余情况均为从1开始出现，直到某个值没有出现

        // 2.从1开始遍历HashMap，输出最早未登记的key
        int i = 2;
        while (hm.containsKey(i)) {
            i++;
        }
        return i;
    }
}