牛客网面试必刷：BM53 缺失的第一个正整数

浅浅的花香味﹌ 2024-03-22 17:57 70阅读 0赞

#### 牛客网面试必刷：BM53 缺失的第一个正整数 ####

*  前言
 *  一、解法1：哈希表

--------------------

## 前言 ##

**给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数**

![在这里插入图片描述][e4de3bf1158148aaa2ac375e20ab06d0.png]

--------------------

## 一、解法1：哈希表 ##

**n个长度的数组，没有重复，则如果数组填满了1～n1～n1～n，那么缺失n+1n+1n+1，如果数组填不满1～n1～n1～n，那么缺失的就是1～n1～n1～n中的数字。对于这种快速查询某个元素是否出现过的问题，还是可以使用哈希表快速判断某个数字是否出现过。**

具体做法：

step 1：构建一个哈希表，用于记录数组中出现的数字。

step 2：从1开始，遍历到n，查询哈希表中是否有这个数字，如果没有，说明它就是数组缺失的第一个正整数，即找到。

step 3：如果遍历到最后都在哈希表中出现过了，那缺失的就是n+1。

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param nums int整型一维数组 
         * @return int整型
         */
        public int minNumberDisappeared (int[] nums) {
        
            // write code here
            if(nums.length == 0) return 1;
            HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
            //哈希表记录数组中出现的每个数字
            for(int i = 0; i < nums.length; i++)
                mp.put(nums[i], 1);
            int res = 1;
            //从1开始找到哈希表中第一个没有出现的正整数
            while(mp.containsKey(res))
                res++;
            return res;
        }
    }

![在这里插入图片描述][f645da232cdd4d69ab081957a62663b8.png]

[e4de3bf1158148aaa2ac375e20ab06d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/63191e0f384a4292aca7573e596622ed.png
[f645da232cdd4d69ab081957a62663b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5f81425f51e54d8ea944ba610d2de8e2.png