缺失的第一个正数
First Missing Positive
本机进度仅保存在当前浏览器
题目描述
给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。要求时间 O(n) 且只使用常数级别的额外空间。
示例：nums = [3, 4, -1, 1]，输出 2；nums = [7, 8, 9, 11, 12]，输出 1。
解题思路
- 答案一定落在 [1, n + 1] 内（n 为数组长度）：最理想的情况是数组恰好装着 1..n。
- 把数组本身当哈希表：让数值 v 回到下标 v - 1（置换 nums[i] = v），用 while 循环不断把当前值换到它该去的位置。
- 注意跳过越界值与重复值，否则死循环；置换完成后第一个 nums[i] != i + 1 的位置即答案。
- 每个值最多被换一次到位，总交换次数 O(n)，满足时间要求。
参考实现
查看参考实现Python · 建议先自行作答
def firstMissingPositive(nums):
n = len(nums)
# 原地置换：让数值 v 回到下标 v-1
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1