41. 缺失的第一个正数 (Hard)
专题归类： 数组 · 哈希表 LeetCode 链接： https://leetcode.cn/problems/first-missing-positive/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。
要求： 时间复杂度 O(n) 且空间复杂度为 O(1)（原地操作）。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：1 和 2 都出现了，缺失的最小正数是 3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
补充说明：
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1- 时间复杂度 O(n)，空间复杂度 O(1)
题目详细分析
数据范围分析：
- 数组长度最大 5×10^5，O(n) 时间可行，O(n log n) 的排序勉强可行但排序后无法保持 O(1) 空间（除非用堆排序）。
- 元素值范围很大（32 位有符号整数），无法用布尔数组标记（空间会太大）。
- 空间 O(1) 意味着不能使用哈希表、集合或布尔数组。
输入输出特征：
- 输入是未排序的整数数组（含负数、零、正数），输出是最小的缺失正整数。
- 答案一定在 [1, n+1] 范围内（n 为数组长度）——因为如果有 n 个数，最小缺失正数最大就是 n+1（当 1~n 都存在时）。
边界条件：
- 数组全部为负数或零 → 最小缺失正数是 1。
- 数组包含 1~n 的所有数 → 答案是 n+1（如 [1,2,3] → 4）。
- 数组包含重复数 → 不影响结果，重复元素就地处理时要注意死循环。
- 数组只有一个元素 → 如果该元素是 1 则答案为 2，否则答案为 1。
隐藏条件：
- “缺失的最小正数”这个定义决定了答案范围是 [1, n+1]，这正是原地哈希的核心依据。
- O(1) 空间限制了只能用数组本身做哈希表，即把值 x 放到索引 x-1 的位置。
- 不需要考虑负数和大于 n 的数，因为它们无法占据 1~n 的位置。
小白版直白理解
想象你们班有 n 个学生，学号从 1 开始编号。老师让你检查：最小的没被使用的学号是多少？
但学号单是乱的，而且有些学号可能不对（负数、0、或者特别大的数字）。
朴素的方法： 拿个本子从 1 开始记，看 1 有没有出现，2 有没有出现……这就是用额外空间。
空间 O(1) 的方法： 把学号单看作 n 个座位，规定”学号为 x 的同学应该坐在第 x 个座位上”（就是索引 x-1）。
- 遍历座位，如果座位上的人坐错了（比如学号 3 坐在了第 1 个座位上），就让他去正确的座位
- 交换后，新来这个座位的人也可能坐错了，继续让他归位
- 全部归位后，再扫描一遍：第一个座位坐的不是学号 1 → 最小缺失就是 1；第二个座位坐的不是学号 2 → 最小缺失就是 2……
为什么范围是 1 到 n+1？ 因为总共只有 n 个位置，最小缺失正数不可能超过 n+1。比如 3 个座位，如果 1、2、3 都有人了，那缺失的就是 4。
解题思路
思路一：原地哈希（推荐）
核心洞察：
答案一定在 [1, n+1] 范围内。我们把数组当作哈希表：
- 值 1 应该放在索引 0
- 值 2 应该放在索引 1
- 值 x（在 [1, n] 内）应该放在索引 x-1
通过交换操作将每个数归位，然后扫描找到第一个位置不对的，就是缺失的最小正数。
def firstMissingPositive(nums):
n = len(nums)
# Step 1: 原地归位
for i in range(n):
# while 循环：不断交换直到当前位置的值归位或无法归位
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# 将 nums[i] 放到它应该在的位置
correct_pos = nums[i] - 1
nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
# Step 2: 扫描找缺失值
for i in range(n):
if nums[i] != i + 1:
return i + 1
# Step 3: 全部归位，说明 1~n 都存在
return n + 1为什么用 while 而不是 if： 交换后，当前位置来了一个新值，这个新值可能也需要归位。while 确保当前位置的值最终要么归位要么不需要归位（负数、0、或 > n）。
复杂度： O(n) 时间（每个元素最多被交换两次），O(1) 空间。
思路二：标记法（另一种原地哈希）
先处理数组中的数，把不在 [1, n] 范围内的数统一替换为一个特殊值（如 n+1）。然后遍历数组，对每个值 x，标记索引 x-1 为负数（表示 x 存在）。最后扫描找到第一个正数索引。
def firstMissingPositive_mark(nums):
n = len(nums)
# Step 1: 将非正数和大于 n 的数替换为 n+1
for i in range(n):
if nums[i] <= 0 or nums[i] > n:
nums[i] = n + 1
# Step 2: 用负号标记存在的数
for i in range(n):
val = abs(nums[i])
if val <= n:
# 将索引 val-1 标记为负数（表示 val 存在）
if nums[val - 1] > 0:
nums[val - 1] = -nums[val - 1]
# Step 3: 找到第一个正数的索引
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1思路三：排序法（不满足要求，但易于理解）
排序后扫描，用 expected = 1 来依次检查。O(n log n) 时间，不满足 O(n) 要求，且排序一般需要 O(n) 额外空间。
def firstMissingPositive_sort(nums):
nums.sort()
expected = 1
for num in nums:
if num == expected:
expected += 1
elif num > expected:
# 出现大于 expected 的数，说明 expected 缺失
return expected
return expected易错点
- 使用 while 而非 if：在交换过程中，当前索引位置获得了新值，必须继续处理直到该位置的值归位或不需要归位。用 if 会导致遗漏。
- 交换顺序：
nums[i], nums[nums[i]-1]这个交换顺序有问题！因为 Python 中右侧的nums[i]会先被计算还是先被赋值？正确写法是用临时变量或先存正确位置：correct_pos = nums[i] - 1; nums[i], nums[correct_pos] = nums[correct_pos], nums[i]。 - 死循环处理：
nums[nums[i] - 1] != nums[i]这个条件防止了死循环——如果目标位置已经有相同的值，说明重复，不需要交换。 - 值范围判断：只处理
1 <= nums[i] <= n的值，负数、0、大于 n 的值不参与交换。 - 索引从 0 开始：值 x 对应索引 x-1，不是 x。这是最常见的 off-by-one 错误。
- 答案范围：如果 1~n 都存在，答案是 n+1，不是 n。
框架提炼
原地哈希通用模板（值映射到索引）：
def firstMissingPositive(nums):
n = len(nums)
# Step 1: 将所有在范围内的值放到正确的位置
# 核心逻辑：值 x (1 <= x <= n) 应该放在索引 x-1
for i in range(n):
while 条件判断(当前位置的值需要归位):
交换(当前位置, 目标位置)
# Step 2: 扫描找到第一个不匹配的位置
for i in range(n):
if nums[i] != i + 1:
return i + 1 # 第一个缺失的正数
# Step 3: 全部匹配
return n + 1条件判断通用形式：
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:原地哈希的适用特征：
- 问题涉及一组值在确定范围内（通常是 [1, n] 或 [0, n-1]）
- 空间复杂度要求 O(1)
- 可以用数组本身代替哈希表
同类原地哈希问题：
- 287-寻找重复数 — 值在 [1, n] 范围内，数组长度 n+1，找重复的数。
- 448-找到所有数组中消失的数字 — 值在 [1, n] 范围内，找没出现的数。
关联题目
- 287-寻找重复数 — 同样是值范围 [1, n] 的原地哈希问题，但找的是重复的数而不是缺失的数。可以用原地哈希或链表判圈法。
- 448-找到所有数组中消失的数字 — 和本题高度相似，标记法可以直接应用。区别在于本题求最小缺失，448 求所有缺失。
- 442-数组中重复的数据 — 也是值范围 [1, n]、用原地标记法找出重复元素。
- 268-丢失的数字 — 更简单版本：值范围 [0, n]，找缺失的一个数，可以用求和公式或异或解。