可视化图解算法70：缺失的第一个正整数

1.题目

描述

给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数

进阶： 空间复杂度 O(1)，时间复杂度 O(n)

数据范围:

-2^31^<=nums[i]<=2^31^-1

0<=len(nums)<=5x10^5^

示例1

输入：

[1,0,2]

返回值：

3

示例2

输入：

[-2,3,4,1,5]

返回值：

2

示例3

输入：

[4,5,6,8,9]

返回值：

1

2. 题解思路

未排序的整数数组nums，需要找到缺失的第一个正整数，可以将数组中的内容添加到set中（主要考虑到set查询的速度优势），同时记录数组中的最大正整数n，之后从1到n遍历整数，对比遍历到的整数是否已经在set中。

具体思路是：

1. 定义一个哈希表（set）；
2. 将数组中的值存储到set中，其中n为数组中最大的数；
3. 从自然数1开始到n，到map中找，如果对应的自然数没有找到，直接返回；
4. [1:n]都在map中，则返回 n + 1。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3.编码实现

核心代码如下：

func firstMissingPositive(nums []int) int {
    //1.定义一个哈希表（set，用map实现set的功能）
    hashTable := make(map[int]struct{}, len(nums))
    n := 1 //数组中最大的数
    //2.将数组中的值存储到map中，key为：数组中的值，value：可以是任意值（没有实际意义），数组中的最大值为n
    for _, v := range nums {
        hashTable[v] = struct{}{}
        if v > n {
            n = v
        }
    }
    //3.从自然数1开始到n，到map中找，如果对应的自然数没有找到，直接返回
    for i := 1; i <= n; i++ {
        if _, ok := hashTable[i]; !ok {
            return i
        }
    }
    //4. 1~n都在map中，则返回 n + 1
    return n + 1
​
}

具体完整代码你可以参考下面视频的详细讲解。

• Python编码：B站@好易学数据结构
• Java编码：B站@好易学数据结构
• Golang编码：B站@好易学数据结构

4.总结

本题的核心其实是统计在数组中未出现的第一个正整数，因此需要用map或者set，相比map来说用set更适合本题。将数组中的内容全部添加到set中，之后对整数1至n到set中查询，查看该整数是否存在。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

✅ 链表

✅ 二叉树

✅ 二分查找、排序

✅ 堆、栈、队列

✅ 回溯算法

✅ 哈希算法

✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：B站@好易学数据结构
• Java编码实现：B站@好易学数据结构
• Golang编码实现：B站@好易学数据结构

对于LeetCode数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：人皆知有用之用，而莫知无用之用也。