yicong@algo:~/code/05-array$ cat 0041-first-missing-positive.cpp
41. 缺失的第一个正数
// 思路
题目最后一句要求 O(n) 时间 + O(1) 额外空间,所以两条常见路线都不合格: - 排序后扫一遍:O(n log n) 时间,不是 O(n); - 哈希集合记录出现过的数:O(n) 时间,但额外空间 O(n)。 整道题的钥匙是一句观察: n 个数,最"满"的情况是 1, 2, 3, ..., n 全都出现了,这时答案就是 n + 1。 所以答案一定落在 [1, n+1] 里。 推论:所有 <= 0 或 > n 的数都不可能成为答案,是垃圾数据,甚至可以直接覆盖掉。 于是问题从"在 [-2^31, 2^31) 里找"压缩到"在 1..n 里找", 而 1..n 恰好和数组下标 0..n-1 一一对应,可以拿数组本身当哈希表。 版本一:哈希集合,最直观,O(n) 时间 O(n) 空间。 版本二(正解):原地哈希(循环排序)。 不变量:让每个在 [1, n] 内的数 v 都待在下标 v-1 上,即最终 nums[v-1] == v。 从左往右扫,每个数只要"不在自己该待的位置上"就把它送回去(交换)。 扫完之后,第一个满足 nums[i] != i+1 的位置 i,答案就是 i+1; 如果全部都在位,答案是 n+1。
// 时间复杂度
版本一:O(n) 版本二:O(n)。每次交换都至少把一个数放到它的最终位置,且之后不会再被赶走, 所以交换总次数 <= n,外层再加一趟扫描,整体线性。
// 空间复杂度
版本一:O(n),哈希集合 版本二:O(1),只用了几个临时变量,直接在原数组上操作
// 易错点
1. 先想清楚"答案在 [1, n+1]",否则不知道该忽略哪些数,也想不出原地哈希。 2. 判重条件必须是 nums[nums[i]-1] != nums[i](目标位置上已经是我了吗), 不能写 nums[i] != i+1。否则遇到重复元素会死循环: nums = [1,1],i=1 时 nums[1]=1 想换到下标 0,但下标 0 上已经是 1,交换后纹丝不动。 3. 边界判断要写在 && 链里靠短路挡住。nums[i] 可能是 -2^31, 先算 nums[i] - 1 会整数溢出(未定义行为)。 4. 里面是 while 不是 if。换到 i 位置的新数可能还需要继续送走。 5. 最后扫描的判断 nums[i] != i+1 和第 2 条的判重条件不是一回事,别混用。 6. 全部都在位时要返回 n+1,不是 n。
// 面试口述要点
1. 先给哈希集合:O(n) 时间 O(n) 空间,说明了答案范围是 [1, n+1]; 2. 再说空间怎么降到 O(1):既然范围就是 1..n,而下标也是 0..n-1, 就把"数 v 出现过"这个信息直接写在 nums[v-1] 上,用数组本身当哈希表; 3. 用循环排序把每个数送回位置,总交换次数不超过 n,所以还是 O(n); 4. 强调判重要用"目标位置是否已经正确",这是处理重复元素的关键。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:哈希集合,最直观,O(n) 时间 / O(n) 空间
// 答案一定在 [1, n+1] 里,所以从 1 开始往上试,第一个没出现过的就是答案
// ================================================================
int firstMissingPositive_v1(vector<int>& nums) {
int n = (int)nums.size();
unordered_set<int> seen; // 记录出现过的正整数
for (int i = 0; i < n; i++) {
if (nums[i] >= 1) { // 负数、0 不可能成为答案,不用记
seen.insert(nums[i]);
}
}
// 从 1 试到 n,第一个不在集合里的就是答案
for (int v = 1; v <= n; v++) {
if (seen.find(v) == seen.end()) {
return v;
}
}
// 1 到 n 全都在,说明答案是 n+1
return n + 1;
}
// ================================================================
// 版本二:原地哈希(循环排序),O(n) 时间 / O(1) 空间,正解
// 不变量:每个在 [1, n] 内的数 v,最后都待在下标 v-1 的位置上
// 注意:这个函数会修改 nums,调用方不要依赖传进来的原数组
// ================================================================
int firstMissingPositive(vector<int>& nums) {
int n = (int)nums.size();
// ---------- 第 1 步:把每个数送回它该待的位置 ----------
for (int i = 0; i < n; i++) {
// 三个条件缺一不可,顺序也不能换:
// 1) nums[i] >= 1 :负数、0 是垃圾数据,跳过
// 2) nums[i] <= n :比 n 大的数是垃圾数据,跳过
// 这两条靠 && 短路挡住,避免下面算 nums[i]-1 时溢出
// 3) nums[nums[i]-1] != nums[i]
// :它该待的位置上还不是它,才需要交换
// 如果已经是它了,交换没有意义,还会死循环
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// 把 nums[i] 换到下标 nums[i]-1 去
swap(nums[i], nums[nums[i] - 1]);
// 用 while 是因为:换到 i 位置的这个新数,可能也还需要继续送走
}
}
// ---------- 第 2 步:找第一个错位的位置 ----------
// 如果原地哈希成功,应该有 nums[i] == i + 1
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1; // 下标 i 上该放 i+1,但它不是
}
}
// ---------- 第 3 步:1 到 n 全都各就各位 ----------
return n + 1;
}
};
// 本地测试:输入 n,然后 n 个整数;输出缺失的最小正整数
// 注意:版本二会修改 nums,所以两个版本各用一份副本
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
vector<int> copy = nums; // 给版本二留一份,避免互相影响
int ans1 = Solution().firstMissingPositive_v1(nums);
int ans2 = Solution().firstMissingPositive(copy);
if (ans1 != ans2) {
cout << "MISMATCH: v1=" << ans1 << " v2=" << ans2 << '\n';
return 0;
}
cout << ans1 << '\n';
return 0;
}