2018·41 未出现的最小正整数：从逐个试探到标记数组

本文是「从暴力解到最优解」专题的第一篇。套路：先把暴力解写对 → 按判分口径估分 → 找浪费 → 升级成最优解。

题目

给定一个含 n（n ≥ 1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 {-5, 3, 2, 3} 中未出现的最小正整数是 1；数组 {1, 2, 3} 中未出现的最小正整数是 4。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

题面写了「时间上尽可能高效」——按总纲的分类，这道题暴力解和最优解之间存在真实分差。总分 15 分。

第一步：把暴力解写对

最直接的想法：答案是「未出现的最小正整数」，那就从 1 开始一个一个试——1 在数组里吗？在，试 2；2 在吗？在，试 3……第一个不在数组里的数就是答案。

动手之前先解决一个问题：**试到几为止？**这里就藏着本题最关键的洞察：

**数组只有 n 个数，所以答案最大不超过 n + 1。**最极端的情况是这 n 个数恰好是 1, 2, …, n，此时答案为 n+1；其余任何情况下，1..n 里至少缺一个，答案 ≤ n。所以候选只有 1 到 n+1 这 n+1 个数，逐个试探一定会停下来。

暴力解成型：

int firstMissingPositive(int A[], int n) {
    // 答案必在 [1, n+1]，从小到大逐个候选试探
    for (int x = 1; x <= n + 1; x++) {
        int found = 0;
        for (int i = 0; i < n; i++) {      // 回到数组里从头找 x
            if (A[i] == x) { found = 1; break; }
        }
        if (!found) return x;              // 第一个找不到的候选就是答案
    }
    return n + 1;                          // 循环内必然返回，此行仅作兜底
}

验证一下题面的两个例子：{-5, 3, 2, 3}——试 1，找不到，返回 1 ✓；{1, 2, 3}——1、2、3 都能找到，试 4 找不到，返回 4 ✓。负数和大于 n 的元素不需要任何特殊处理，它们只是「找的时候永远匹配不上」而已。

复杂度：外层最多 n+1 个候选，内层每次扫整个数组，时间 $O (n^{2})$ ；没开任何辅助结构，空间 $O (1)$ 。

它值多少分

408 算法设计题的判分拆成两个维度（详见总纲）：

正确性（占大头）：上面这份暴力解，设计思想说得清（含「答案必在 [1, n+1]」这个关键洞察）、代码逻辑自洽、复杂度分析 $O (n^{2})$ 与实现一致——正确性维度的分都能拿到。
最优性（小头）：题面要求「时间上尽可能高效」，期望复杂度是 $O (n)$ 。 $O (n^{2})$ 达不到，这一档拿不到。

也就是说：这份暴力解交上去，这道 15 分的题主体分在手，只在最优性那一小档上丢分。注意复杂度那一问要照实写 $O (n^{2})$ ——「分析与算法一致」本身是正确性得分点，谎报 $O (n)$ 反而丢正确性的分。

暴力解的浪费在哪

用总纲的三个问题审一遍这份代码：

**有没有重复扫描？——有，而且很严重。**试探候选 1 时把数组扫了一遍，试探候选 2 时又从头扫一遍……数组内容从头到尾没变过，我们却反复地扫它。每一遍扫描只带走一个 bit 的信息（「x 在不在」），扫完就扔。

换个角度看：第一遍扫描时，其实每个元素都已经从眼前过了一次。A[i] = 3 这个事实，在试探候选 3 的时候要用——但暴力解在第一遍看到它时没有记下来，于是后面只能重新去找。

浪费的本质：看见过的信息没有存下来，导致同样的查询反复触发全表扫描。

智慧化改造：把「见过谁」记下来

对策是总纲里的第二类手段——空间换时间。既然候选只有 1..n+1，那就开一个长度 n+1 的标记数组 mark[]，扫数组一遍，看见落在 [1, n] 范围内的值 v 就置 mark[v] = 1（值直接当下标用， $O (1)$ 一次记录）。之后回答「x 出现过吗」只需查 mark[x]，全表扫描消失了。

原来的「n+1 个候选 × 每个扫全表」变成「扫一遍记录 + 扫一遍标记找答案」：

#include <stdlib.h>

int firstMissingPositive(int A[], int n) {
    char *mark = (char *)calloc(n + 1, sizeof(char));   // 下标 0 不用，1..n 标记是否出现
    if (mark == NULL) return -1;                        // 分配失败保护

    // ① 第一段：扫 A 一遍，把 1..n 范围内的数标记
    for (int i = 0; i < n; i++) {
        if (A[i] >= 1 && A[i] <= n) {
            mark[A[i]] = 1;
        }
    }

    // ② 第二段：从 1 起找第一个未标记的下标
    int ans = n + 1;                                    // 1..n 全出现则答案为 n+1
    for (int i = 1; i <= n; i++) {
        if (!mark[i]) { ans = i; break; }
    }

    free(mark);
    return ans;
}

从暴力解升级过来时，有三个细节容易踩坑：

过滤范围 [1, n] 必不可少。暴力解里负数和大数天然无害，但换成「值当下标」后，mark[-5] 或 mark[10⁹] 直接越界。升级方法时，原来免费得到的安全性要重新自己保证——这是「暴力升级最优」时的普遍现象。
标记数组初值必须全 0。用 calloc（自动清零）；用 malloc 不清零会读到残留值，把没出现的数误判成出现过。
答案 n+1 的兜底。第二段扫完 1..n 全被标记时返回 n+1，对应 {1, 2, 3} 这种情形。

复杂度：两段各扫一遍，时间 $O (n)$ ；辅助数组 n+1 字节，空间 $O (n)$ 。这就是本题的标准答案，正确性、最优性两个维度全部拿满。

两版对照跑一遍

同一组输入 [3, -1, 4, 1, 6, 2]（答案 5），先看暴力解——注意每个候选都触发一轮完整的内层扫描：

加载可视化中...

再看标记数组版——两段线性扫描，步数明显少了一个量级：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

排序后扫描：排完序从头找第一个「断档」。思路正确，拿正确性分； $O (n \log n)$ 没到 $O (n)$ ，最优性那档拿不到——它相当于只回答了「重复扫描」的浪费，没用上「候选范围只有 [1, n+1]」这个性质。
哈希表：和标记数组同为 $O (n)$ ，判分等价；但值域已知且连续时，数组就是最朴素的哈希，常数更小、代码更短。
原地置换（进阶）：把 A[i] 交换到下标 A[i]−1 的位置上，可以做到 $O (n)$ 时间 + $O (1)$ 辅助空间。标准答案没有要求它，写到标记数组即拿满分；卷面有余力可以提一句作为加分项。

下一步

在 OJ 上把两版代码都提交跑一遍：ds-2018-41 未出现的最小正整数
回到题库看这道题的完整解析与错因：真题库 · 数据结构
同一优化手段（标记数组/空间换时间）的另一道真题：2015·41 链表按绝对值去重，专题后续更新

2018·41 未出现的最小正整数：从逐个试探到标记数组 ​

题目 ​

第一步：把暴力解写对 ​

它值多少分 ​

暴力解的浪费在哪 ​

智慧化改造：把「见过谁」记下来 ​

两版对照跑一遍 ​

等价方法与升级空间 ​

下一步 ​