E30646: 缺失的第一个正数

hash table, http://cs101.openjudge.cn/practice/30646

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

输入

总共两行，第一行一个正整数n（1 ≤ n ≤ 100），第二行n个整数，用空格隔开，代表数组nums。

输出

输出一个整数，代表数组nums中没有出现的最小正整数。

样例输入

3
1 2 0

样例输出

提示：-2^31 <= nums[i] <= 2^31 - 1

来源：2026 spring TA-wjl. T41, https://leetcode.cn/problems/first-missing-positive/

由于题目给出的数据范围较小（ $n \leq 100$ ），可以使用 Python 的集合（set）来高效地解决。

解题思路

理解“最小正整数”：正整数是从 1 开始的（1, 2, 3, ...）。需要找到数组中不存在的最小的那个。
利用集合去重与加速查找：
- 将输入的数组转换为一个集合 set。在 Python 中，集合的查找操作（in）平均时间复杂度是 $O (1)$ ，非常快。
从 1 开始枚举：
- 从数字 1 开始检查，看它是否在集合中。
- 如果 1 在集合中，我们就检查 2；如果 2 也在，就检查 3……以此类推。
- 第一个不在集合中的正整数就是我们要找的答案。
复杂度分析：
- 时间复杂度： $O (n)$ ，其中 $n$ 是数组长度。建立集合需要 $O (n)$ ，遍历查找最多也只需要 $n + 1$ 次。
- 空间复杂度： $O (n)$ ，用于存储集合。

Python 代码实现

python

import sys

def solve():
    # 读取所有输入并按空格切分
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 第一行是 n，后面是 n 个整数
    n = int(input_data[0])
    # 将数组元素转为整数并放入集合中
    nums = set(map(int, input_data[1:n+1]))
    
    # 从最小的正整数 1 开始查找
    res = 1
    while res in nums:
        res += 1
    
    # 输出结果
    print(res)

if __name__ == "__main__":
    solve()

E30646: 缺失的第一个正数 ​

E30646: 缺失的第一个正数