题目

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

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：开一个长度为 n+1 的辅助标记数组 mark[]，扫一遍原数组，若 A[i] ∈ [1, n] 则置 mark[A[i]] = 1；再从 1 扫到 n，第一个 mark[i] == 0 的 i 即答案；若 1..n 全被标记，答案是 n+1。

为什么答案一定 ∈ [1, n+1]？

数组共 n 个数。最理想情况是这 n 个数恰好是 1, 2, ..., n（最小未出现正整数 = n+1）；其他任何情况下，1..n 中至少有一个没出现，答案 ≤ n。所以答案落在 [1, n+1] 这个 n+1 个候选里——只需关心 1..n 是否出现，大于 n 的元素和非正数都对答案没贡献，可以直接忽略。

为什么需要 mark 数组？

• 排序后扫描？O(n log n)，慢一档；
• Hash 表？复杂度同 O(n)，但常数大、写起来繁；
• 直接拿值当下标：mark[A[i]] = 1 是 O(1)，n 个元素累计 O(n)。这是本题的最优解。

两段扫描：

1. 第一段（标记）：遍历 A，若 1 ≤ A[i] ≤ n 就在 mark[A[i]] 置 1；否则跳过；
2. 第二段（找答案）：i 从 1 扫到 n，遇到第一个 mark[i] == 0 即返回 i；扫完都被标记则返回 n+1。

(2) 代码实现

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

关键点说明：

• 过滤负数和 > n 的元素：第一段判断 A[i] >= 1 && A[i] <= n 必不可少，否则 mark[A[i]] 越界、负下标或写 mark[10⁹]，立刻段错误。
• mark 用 char 而非 int：每个槽位只需 0/1，用 char 省 4 倍空间；calloc 自动清零。
• 答案 = n+1 的兜底：第二段循环结束没找到未标记的下标，说明 1..n 全部出现，下一个最小未出现正整数就是 n+1。
• 不要被 A[i] 是负数的例子吓到：题面例子 {-5, 3, 2, 3}，−5 直接被过滤；mark 中只有 mark[2]=1, mark[3]=1，扫 1..4 时 i=1 处 mark=0 → 返回 1 ✓。

(3) 复杂度分析

• 时间复杂度 ：两段循环各扫一次数组（一段长 n，一段长 n），常数次操作。
• 空间复杂度 ：辅助数组 mark 占 n+1 字节。这是本题的标准答案。

编者注（生僻术语）：本题有一种 时间 + 空间的"原地标记"高级解法——把 A[i] 与 A[A[i]−1] 交换，使每个 1..n 的值落到对应下标，最后扫一遍即可。考研标准答案不要求做到 空间，写到 就拿满分；如果有时间余力可以提一句"亦可用原地置换降到 辅助空间"加分。