缺失的第一个正数
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先想暴力：用哈希集合记录 nums 里所有正数，再从 1 开始递增找第一个不在集合里的——正确，但需要 O(n) 额外空间，不满足题意。
2. 重复在哪里？我们其实只关心 1..n 哪些出现了；大于 n 的数和 ≤0 的数都是噪声，可以忽略。
3. 关键转化：把数组当成长度为 n 的哈希桶——值 x（1≤x≤n）应该放在下标 x-1。对每个位置 i，若 nums[i] 是合法值且还没在正确位置，就与 nums[nums[i]-1] 交换，直到当前位无法继续换。
4. 例 2 [3,4,-1,1]：i=0 把 3 换到 index 2 → [−1,4,3,1]；i=1 把 4 换到 index 3 → [−1,1,3,4]；i=1 再把 1 换到 index 0 → [1,−1,3,4]。第二遍扫描：nums[1]=−1≠2，答案 2。
5. 为什么 while 不会死循环？每次交换都让某个合法值到达最终位置，每个下标最多被「填对」一次，总交换次数 O(n)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
n | int | 定义：数组长度，答案只可能落在 [1, n+1]维护：有效正整数 x 若存在，必在 1..n 内（大于 n 的数不可能是最小缺失正数）更新：初始化后不变，用于界定「该放哪里」与最终扫描上界 |
i | int | 定义：当前正在整理的数组下标 维护：从左到右扫，保证 nums[0..i-1] 已就位（nums[j]==j+1）更新：当前位置元素归位或判定为垃圾后 i++ |
nums[k] | int | 定义：下标 k 处的值；语义上应存放整数 k+1（若该数存在于原数组）维护：把每个合法值 x∈[1,n] 交换到 nums[x-1]，形成「值 x 住在下标 x-1」的原地哈希表更新：通过 swap(nums[i], nums[nums[i]-1]) 循环搬运，直到 nums[i] 不在 [1,n] 或已在正确位置 |
ans | int | 定义：第一个缺失的正整数 维护：第二遍扫描找最小 i 使 nums[i] != i+1，则 ans = i+1更新：若 1..n 全在位，ans = n+1 |
落码步骤
1. 令 n = len(nums)，第一遍原地整理：对 i 从 0 到 n-1
2. 当 1 ≤ nums[i] ≤ n 且 nums[i] ≠ nums[nums[i]-1] 时，交换 nums[i] 与 nums[nums[i]-1]（把 nums[i] 送到它应在的下标）
3. 内层 while 结束说明当前位已是垃圾值（≤0 或 >n）或已就位，i++ 处理下一位
4. 第二遍扫描：找最小 i 使 nums[i] ≠ i+1，返回 i+1
5. 若 1..n 全部在位，返回 n+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 + 1class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
int j = nums[i] - 1;
swap(nums[i], nums[j]);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
};
// 时间 O(N)，空间 O(1)复杂度分析
O(N)（每个元素最多被交换到正确位置一次）
O(1)（只用常数额外变量，原地修改数组）
常见坑
用 if 只交换一次：例如 [3,4,-1,1] 在 i=0 换完后当前位仍是 3 的「错值」，必须用 while 持续交换直到无法继续。
忘记判重 nums[i] != nums[nums[i]-1]：若目标位已是相同值（重复数字），再交换会死循环。
第二遍扫描条件写错：应比较 nums[i] != i+1，不是 nums[i] != i；下标从 0 开始，期望存放的是 i+1。
必测边界 Case
nums = [-1,-2,-3] → 1（没有任何正数，最小缺失正数为 1）
nums = [1,2,3] → 4（1..n 都在，答案为 n+1）
nums = [3,4,-1,1] → 2（-1 与重复值被留在错误位置，不影响扫描）
nums = [7,8,9,11,12] → 1（没有任何 1..n 的有效值）
nums = [1] → 2；nums = [2] → 1