1. 概述
本文将探讨几种不同的算法，用于在整数数组中查找最小的缺失正整数。
首先，我们会明确问题定义。接着，介绍三种可行的解决方案。最后，分析它们的时间与空间复杂度，帮助你在实际场景中做出合理选择。
2. 问题定义
目标很明确：在一个由非负整数组成的数组中，找出最小的未出现的正整数。更准确地说，对于一个长度为 n 的数组，我们要找的是范围 [0, n-1] 内第一个缺失的整数。如果这个范围内的所有整数都存在，则答案就是 n。
✅ 举个例子：
- 数组
[0, 1, 3, 5, 6]长度为 5，我们需要检查0~4的数字。其中2缺失，因此答案是2。 - 数组
[0, 1, 2, 3]长度为 4，0~3全部存在，因此答案是4。
⚠️ 注意：虽然问题描述中提到了 0，但通常这类问题关注的是“正整数”，不过根据示例逻辑，实际是从 0 开始查找。我们按题意处理，即包含 0。
3. 有序数组中的查找
如果数组已经排序，问题就变得简单粗暴了：遍历数组，第一个 index != value 的索引就是答案。
比如数组 [0, 1, 3, 4, 6, 7]：
Index: 0 1 2 3 4 5
Value: 0 1 3 4 6 7
索引 2 处的值是 3，不等于 2，所以 2 就是最小缺失整数。
实现代码
我们创建一个工具类 SmallestMissingPositiveInteger，并实现方法：
public class SmallestMissingPositiveInteger {
public static int searchInSortedArray(int[] input) {
for (int i = 0; i < input.length; i++) {
if (i != input[i]) {
return i;
}
}
// 所有 0~n-1 都存在，返回 n
return input.length;
}
}
测试验证
// 缺失 3
int[] input = new int[] {0, 1, 2, 4, 5};
int result = SmallestMissingPositiveInteger.searchInSortedArray(input);
assertThat(result).isEqualTo(3);
// 不缺失任何数
int[] input2 = new int[] {0, 1, 2, 3, 4, 5};
int result2 = SmallestMissingPositiveInteger.searchInSortedArray(input2);
assertThat(result2).isEqualTo(input2.length); // 返回 6
4. 无序数组的处理
对于无序数组，有几种思路：
- 先排序，再复用有序数组的算法
- 使用一个布尔数组标记已出现的数字
4.1. 先排序再查找
思路简单：调用 Arrays.sort() 排序后，复用 searchInSortedArray()。
public static int searchInUnsortedArraySortingFirst(int[] input) {
Arrays.sort(input);
return searchInSortedArray(input);
}
测试用例
// 无序且缺失 1 和 3，最小缺失是 1
int[] input = new int[] {4, 2, 0, 5};
int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input);
assertThat(result).isEqualTo(1);
// 完整数组
int[] input2 = new int[] {4, 5, 1, 3, 0, 2};
int result2 = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input2);
assertThat(result2).isEqualTo(input2.length); // 返回 6
4.2. 使用布尔数组标记
使用一个长度为 n 的 boolean[] flags，遍历原数组，对每个值 x，如果 x < n，则 flags[x] = true。最后遍历 flags，第一个 false 的索引就是答案。
public static int searchInUnsortedArrayBooleanArray(int[] input) {
boolean[] flags = new boolean[input.length];
// 标记存在的数字
for (int number : input) {
if (number < flags.length) {
flags[number] = true;
}
}
// 查找第一个缺失的
for (int i = 0; i < flags.length; i++) {
if (!flags[i]) {
return i;
}
}
return flags.length;
}
测试验证
int[] input = new int[] {4, 2, 0, 5};
int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input);
assertThat(result).isEqualTo(1); // 正确返回 1
int[] input2 = new int[] {4, 5, 1, 3, 0, 2};
int result2 = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input2);
assertThat(result2).isEqualTo(input2.length); // 返回 6
5. 复杂度分析
我们使用大 O 表示法来评估性能。
5.1. 有序数组算法
- ✅ 时间复杂度：O(n)
最坏情况是遍历整个数组。 - ✅ 空间复杂度：O(1)
无需额外空间。
5.2. 先排序再查找
- ⚠️ **时间复杂度：O(n log n)**（平均）
Java 11 的Arrays.sort()使用双轴快排，平均 O(n log n)，最坏 O(n²)。 - ✅ 空间复杂度：O(log n)
快排递归栈空间。
踩坑提醒：如果数组接近有序或重复多，快排可能退化到 O(n²)，需注意数据特征。
5.3. 布尔数组法
- ✅ 时间复杂度：O(n)
两次遍历，常数倍忽略，即 O(n)。 - ❌ 空间复杂度：O(n)
额外创建一个长度为 n 的布尔数组。
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 有序数组 | O(n) | O(1) | 输入已排序 |
| 先排序 | O(n log n) | O(log n) | 内存敏感，可接受稍慢 |
| 布尔数组 | O(n) | O(n) | 追求速度，内存充足 |
6. 总结
本文介绍了三种查找最小缺失正整数的算法：
- 有序数组：简单直接，线性扫描。
- 先排序：牺牲时间换空间，适合内存受限场景。
- 布尔数组：时间最优，空间换时间的典型。
实际开发中，选择哪种方案取决于：
- 数据是否已排序
- 对时间 or 空间的敏感度
- 数据规模
完整代码示例已上传至 GitHub 仓库：https://github.com/baeldung/java-algorithms（路径：algorithms-miscellaneous-4）