yicong@algo: ~/code/05-array/0041-first-missing-positive.cpp

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;
}