在数据结构与算法的面试中，有一个经典问题经常被用来考察候选人对数组操作以及时间空间复杂度权衡的理解：在未排序的数组中找出缺失的最小正整数。
如果不仔细思考，我们可能会觉得这需要额外的空间或者复杂的嵌套循环。但实际上，通过巧妙的思路，我们可以把时间复杂度优化到线性级别 O(n)，甚至可以将空间复杂度降低到 O(1)。在这篇文章中，我将带你从最直观的“朴素解法”出发，逐步深入探讨最高效的“预期解法”，并一起分析其中蕴含的算法智慧。无论你是正在准备面试，还是想提升编码能力，这篇深度解析都将为你提供实用的见解。
问题重述
首先，让我们明确一下问题的具体要求。给定一个包含 $N$ 个整数的未排序数组 arr[]，其中可能包含正数、负数甚至零。我们的任务是编写一个函数，找出数组中缺失的最小正整数。
关键点提示：
- 最小正整数：我们从 1 开始找，如果 1 不在数组中，答案就是 1；如果在，就找 2，依此类推。
- 未排序数组：这意味着我们不能依赖顺序，必须通过遍历来处理数据。
- 空间与时间的权衡：这是本题的核心考点。
#### 示例演示
为了让你更直观地理解，我们来看几个例子：
> 示例 1：
> 输入： arr[] = [2, -3, 4, 1, 1, 7]
> 输出： 3
> 解释： 我们看正整数序列：1, 2, 3, 4… 数组中有 1, 2, 4, 7。虽然 1 重复了，2, 4, 7 都存在，但是 3 缺失了。所以答案是 3。
> 示例 2：
> 输入： arr[] = [5, 3, 2, 5, 1]
> 输出： 4
> 解释： 数组包含 1, 2, 3, 5。最小的缺失正整数是 4。
> 示例 3：
> 输入： arr[] = [-8, 0, -1, -4, -3]
> 输出： 1
> 解释： 数组中全是负数或零。那么最小的正整数 1 肯定是缺失的。
方法一：朴素解法（排序法）
当我们面对一个乱糟糟的未排序数组时，最直接的想法往往就是：“能不能先把它排好序？”。确实，排序能让问题瞬间变得简单。
#### 思路解析
- 排序：首先，我们将数组
arr[]进行升序排序。排序后，负数和零会排在最前面，正数跟在后面。 - 初始化目标：既然我们要找最小的正整数，那我们就从 1 开始找。我们定义一个变量
res，初始值为 1。 - 线性扫描：我们遍历排序后的数组。
– 情况 A：如果当前数字等于 INLINECODE8edf4a69（比如找到了 1），说明这个数不缺。我们将 INLINECODEaf922637 加 1（现在开始找 2）。注意：如果数组有重复的 1，我们需要跳过，所以如果 INLINECODEcb4a37a4，我们才递增，如果只是小于 INLINECODEac027b7a，我们直接跳过即可（因为上一轮已经处理过了）。
– 情况 B：如果当前数字小于 res，说明它是重复项或者是负数，直接跳过，继续下一个。
– 情况 C：如果当前数字大于 INLINECODEce2abed8，说明中间出现了断层。例如 INLINECODE4ccb7a46 是 3，但当前数字是 5。这意味着 3 肯定不在数组里（因为数组是递增的，当前都 5 了，后面只会更大）。既然找不到 3，我们就直接返回当前的 res。
#### 复杂度分析
- 时间复杂度：$O(N \log N)$。主要的性能瓶颈在于排序算法（如快速排序或归并排序）。
- 空间复杂度：$O(1)$。如果我们使用像堆排序这样的原地排序算法，除了存储输入数组外，不需要额外的辅助空间。
虽然这种方法不是最快的，但在面试中，如果你一时想不出最优解，先给出这个方案并解释其复杂度，也是一种很好的策略，这体现了你化繁为简的能力。
#### 代码实现
让我们看看如何用不同的编程语言实现这个逻辑。注意代码中的注释，它们详细解释了每一步的操作。
C++ 实现
#include
#include
#include
using namespace std;
// 函数：寻找缺失的最小正整数
int missingNumber(vector &arr) {
// 步骤 1: 对数组进行原地排序，时间复杂度为 O(N*log N)
sort(arr.begin(), arr.end());
// 步骤 2: 初始化结果为 1（最小的正整数）
int res = 1;
// 步骤 3: 遍历排序后的数组
for (int i = 0; i res) {
// 找到了断层，直接返回当前缺失的数字
break;
}
// 如果 arr[i] < res，说明是负数、零或重复数字，直接忽略
}
return res;
}
int main() {
vector arr = {2, -3, 4, 1, 1, 7};
// 预期输出: 3
cout << "缺失的最小正整数是: " << missingNumber(arr) << endl;
return 0;
}
Java 实现
import java.util.Arrays;
class GfG {
static int missingNumber(int[] arr) {
// Java 提供了便捷的工具类进行排序
Arrays.sort(arr);
// 初始化寻找目标为 1
int res = 1;
for (int i = 0; i res) {
break;
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {5, 3, 2, 5, 1};
// 预期输出: 4
System.out.println("缺失的最小正整数是: " + missingNumber(arr));
}
}
Python 实现
def missingNumber(arr):
# Python 的 sort() 非常简洁且高效
arr.sort()
# res 存储当前缺失的最小正整数，初始设为 1
res = 1
for num in arr:
# 如果我们在数组中找到了 ‘res‘
if num == res:
# 更新 res 以寻找下一个数字
res += 1
# 如果当前数字大于 ‘res‘，说明 ‘res‘ 肯定缺失了
elif num > res:
break
return res
if __name__ == "__main__":
arr = [2, -3, 4, 1, 1, 7]
print(f"缺失的最小正整数是: {missingNumber(arr)}")
方法二：进阶思路（哈希/访问数组）
如果我们不关心排序，而是只关心“某个数字是否存在”，那么哈希表或者标记数组是一个好办法。
这个思路的核心在于：先找出所有正数，然后记录哪些正数出现过。
#### 思路解析
- 构建标记：我们可以创建一个辅助数组（或者叫访问数组 INLINECODE17d099cc），大小为 INLINECODE363e201d（假设答案最大只可能是 N+1）。
- 过滤与标记：遍历原数组，对于每一个正整数 INLINECODE9e10c935（在 INLINECODEa4e01dfe 到 INLINECODE8fb8a256 范围内），我们将 INLINECODE6305b431 标记为
true。 - 查找缺失：最后从 INLINECODE63b865ae 开始遍历 INLINECODE693bac24 数组，第一个值为 INLINECODE5a493d7c 的下标就是我们要找的答案。如果都为 INLINECODE34020d6d，则返回
N+1。
#### 复杂度分析
- 时间复杂度：$O(N)$。我们只需要遍历数组两次，这比排序快多了。
- 空间复杂度：$O(N)$。我们需要额外的数组来存储标记。这是典型的“空间换时间”策略。
方法三：最优解法（数组下标标记法 / 循环排序思想）
你可能会问：“有没有既快（$O(N)$）又省空间（$O(1)$）的方法？” 答案是肯定的！这是本题的皇冠上的明珠。
#### 核心洞察
这个方法利用了数组本身的下标来存储信息。这是一个非常巧妙的技巧：对于长度为 INLINECODE423e624d 的数组，如果其中不缺失任何正整数，那么它应该包含 INLINECODEb7611811 到 INLINECODE82253013 的所有数字。我们可以尝试把数字 INLINECODE41bc71fd 放在下标为 i-1 的位置上（例如数字 1 放在 index 0，数字 2 放在 index 1）。
由于我们不想使用额外的数组，我们直接在原数组上进行操作，通过修改数组元素的正负号或者交换位置来达到标记的目的。
#### 思路解析（符号标记法）
这是一种非常优雅的解法，分为两个阶段：隔离 和 标记。
阶段 1：隔离非正数
我们要找的是正整数，所以负数和零对我们要找的答案（至少是1）没有直接贡献。我们可以把负数和零先忽略掉，或者在逻辑上把它们看作“无效空间”。但更简单的做法是：我们只在 1 到 N 的范围内寻找答案。
阶段 2：标记存在的数字
- 我们遍历数组。对于当前元素 INLINECODE8590f6b8，假设其绝对值为 INLINECODE28fd14af。
- 如果 INLINECODE83828ce8 在 INLINECODE70bfd90d 到
N的范围内：
– 我们将 INLINECODE30b4dddc（即对应下标的位置）标记为“已访问”。为了不覆盖原数据（因为我们可能还需要它的值），我们通常将 INLINECODE22b74965 变为负数。
– 如果它已经是负数了，就保持不变（防止重复翻转变正）。
- 如果 INLINECODEaf30c472 是负数或大于 INLINECODE1e4d6627，我们就不管它。
阶段 3：扫描结果
再次遍历数组。找到第一个下标 INLINECODEfd97bc2a，使得 INLINECODEfc582f07 是正数。这意味着 INLINECODE6d7d5f1a 这个数字从未被访问过（即从未在数组中出现）。返回 INLINECODE57027282。
#### 复杂度分析
- 时间复杂度：$O(N)$。我们遍历了几次数组，但都是线性的。
- 空间复杂度：$O(1)$。我们只用了常数级别的额外变量（如循环变量），直接在原数组上修改。
#### 代码实现（最优解）
让我们用 C++ 来实现这个精妙的方法。
#include
#include
#include // 用于 abs()
using namespace std;
// 辅助函数：分离非正数（可选步骤，但在本题逻辑中通过判断即可隐式实现）
// 这里我们直接采用“标记下标”的策略
int missingNumberOptimal(vector &arr) {
int n = arr.size();
// 第一步：遍历数组，使用元素作为下标来标记访问
// 我们将 arr[val - 1] 设为负数，表示 val 存在于数组中
for (int i = 0; i 0 && val 0) {
// 标记为“已访问”：将其变为负数
arr[val - 1] = -arr[val - 1];
}
}
}
// 第二步：再次遍历，寻找第一个正数元素
// 正数元素的下标 + 1 就是我们缺失的数字
for (int i = 0; i 0) {
return i + 1;
}
}
// 如果所有位置都被标记了（都是负数），说明缺失的是 n + 1
return n + 1;
}
int main() {
vector arr = {2, -3, 4, 1, 1, 7}; // 注意：这个例子中有重复和负数
// 注意：由于我们的算法会修改原数组，如果需要保留原数组，请先拷贝一份
// 这里为了演示，直接传入
cout << "缺失的最小正整数是: " << missingNumberOptimal(arr) << endl;
return 0;
}
代码详解：
- INLINECODEf72fc6fc：这很关键。因为当我们处理某个数字 INLINECODE3db4c512 时，我们会把 INLINECODE5a8b6772 的数变成负数。如果后面遍历到了 INLINECODE41c120a5，我们需要它的原始值（如果还没被标记过）或者忽略它（如果已被标记）。取绝对值保证了我们把“值”和“符号”分开了对待。
- INLINECODE39c470ac 判断：防止多次翻转。例如数组 INLINECODE39ec6938。第一个 INLINECODE56264f11 把 INLINECODEe00bf6f8 变成 INLINECODE27528746。遇到第二个 INLINECODEd27015f3 时，
arr[0]已经是负数了，不需要再变一次，否则又变回正数了。
总结与建议
在这篇文章中，我们探索了寻找缺失最小正整数的三种主要方法。
- 排序法 ($O(N \log N)$)：最符合直觉，实现简单。适合数据量较小或面试初期用于展示基本思路。
- 哈希/辅助数组法 ($O(N)$ 空间)：思路清晰，但消耗额外内存。在实际工程中，如果内存不是瓶颈，这是一个非常稳健的选择，因为它不会破坏原始数据。
- 原地标记法 ($O(N)$ 时间 $O(1)$ 空间)：算法面试中的“满分”答案。它展示了对数组下标和数字之间关系的深刻理解，以及通过符号位进行位运算/标记的技巧。
#### 实际应用与最佳实践
- 边界条件检查：在写代码时，永远不要忘记处理空数组或者全是负数的数组。在最优解法中，如果全是负数，循环不会标记任何位置，第二次遍历直接在 INLINECODE5f1eac75 处返回 INLINECODE1970bbb4。
n- 数据完整性：原地修改数组的方法虽然省空间，但会破坏输入数据。在实际的软件开发中，除非明确允许修改输入，否则应该优先考虑非破坏性的算法，或者先拷贝一份数据。
希望这篇深度解析能帮助你不仅解决这道题，更能理解算法设计中“权衡”的艺术。下次当你看到需要 $O(N)$ 时间和 $O(1)$ 空间的问题时，不妨想想：“我能不能利用数组本身作为哈希表？”