LeetCode 题解工作台
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1： 输入： nums = [1,2,0] 输出： 3 解释： 范围 [1,2] 中的数字都在数组中。 示例 2： 输入： nums = [3,4…
2
题型
9
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们假设数组 长度为 ，那么最小的正整数一定在 $[1, .., n + 1]$ 之间。我们可以遍历数组，将数组中的每个数 交换到它应该在的位置上，即 应该在的位置为 $x - 1$。如果 不在 $[1, n + 1]$ 之间，那么我们就不用管它。 遍历结束后，我们再遍历数组，如果 不等于 ，那么 就是我们要找的最小的正整数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
解题思路
方法一：原地交换
我们假设数组 长度为 ，那么最小的正整数一定在 之间。我们可以遍历数组，将数组中的每个数 交换到它应该在的位置上，即 应该在的位置为 。如果 不在 之间，那么我们就不用管它。
遍历结束后，我们再遍历数组，如果 不等于 ，那么 就是我们要找的最小的正整数。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is swapped at most once. Space complexity is O(1) since swaps are done in-place and no extra arrays or hash tables are used. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Focuses on in-place reordering and mapping to indices.
- question_mark
Checks if candidate solutions avoid extra memory usage.
- question_mark
Wants candidates to handle negatives, zeros, and large positive gaps correctly.
常见陷阱
外企场景- error
Swapping incorrectly can lead to infinite loops or missed numbers.
- error
Ignoring numbers outside [1,n] range causes wrong results.
- error
Failing to return n+1 when all slots 1..n are filled.
进阶变体
外企场景- arrow_right_alt
Find the first missing positive when duplicates exist in nums.
- arrow_right_alt
Find all missing positives up to the maximum number in the array.
- arrow_right_alt
Find missing positives under memory constraints stricter than O(1).