0041. First Missing Positive¶
题目信息¶
- 题号:
缺失的第一个正数
- 难度:
Hard
- 主题:
数组、哈希集合、原地哈希、循环置换
- 原题:
- 重点:
从记录正整数是否出现,推导到用数组下标充当值域槽位,并在线性时间内完成原地归位
题目重述¶
给定一个未排序整数数组 nums,返回其中没有出现的最小正整数。
算法必须达到 O(n) 时间复杂度,并且只使用 O(1) 额外空间。允许原地修改数组。
数组长度位于 [1, 10^5],元素可以是任意 32 位有符号整数,因此可能包含负数、零、重复正数以及远大于数组
长度的数。
自建示例¶
nums = [3, 4, -1, 1],返回2;nums = [1, 2, 0],返回3;nums = [7, 8, 9, 11, 12],返回1;nums = [1, 1, 2, 2],返回3;nums = [1, 2, 3, 4],返回5。
C++ 实现¶
#include <algorithm>
#include <unordered_set>
#include <vector>
class Solution {
private:
int sortAndScan(std::vector<int> nums) {
std::sort(nums.begin(), nums.end());
int expected = 1;
for (int value : nums) {
if (value < expected) {
continue;
}
if (value == expected) {
++expected;
continue;
}
break;
}
return expected;
}
int recordWithHashSet(const std::vector<int>& nums) {
std::unordered_set<int> present;
const int n = static_cast<int>(nums.size());
for (int value : nums) {
if (value >= 1 && value <= n) {
present.insert(value);
}
}
for (int candidate = 1; candidate <= n; ++candidate) {
if (present.count(candidate) == 0) {
return candidate;
}
}
return n + 1;
}
int placeValuesIntoOwnSlots(std::vector<int>& nums) {
const int n = static_cast<int>(nums.size());
for (int index = 0; index < n; ++index) {
while (nums[index] >= 1 && nums[index] <= n) {
const int target = nums[index] - 1;
if (nums[target] == nums[index]) {
break;
}
std::swap(nums[index], nums[target]);
}
}
for (int index = 0; index < n; ++index) {
if (nums[index] != index + 1) {
return index + 1;
}
}
return n + 1;
}
public:
int firstMissingPositive(std::vector<int>& nums) {
return placeValuesIntoOwnSlots(nums);
}
};
题解¶
排序扫描¶
排序后从 expected = 1 开始扫描:
当前值小于
expected,它是非正数或重复值,直接跳过;当前值等于
expected,说明该正整数存在,令expected加一;当前值大于
expected,有序性保证后面不会再出现expected,可以停止。
sortAndScan 准确表达了“从 1 开始寻找首个缺口”,但排序需要 O(n log n) 时间。
有效答案范围¶
长度为 n 的数组中,答案只可能位于 [1, n + 1]。
若 1 到 n 中有任意一个值缺失,最小缺失正整数必然在该范围内;若它们全部出现,答案就是 n + 1。
因此负数、零和大于 n 的值都与答案判定无关。
recordWithHashSet 只记录 [1, n] 中出现过的值,再从 1 到 n 查询首个缺失项。它把时间降到
O(n),但集合需要 O(n) 额外空间。
下标槽位¶
数组本身已有 n 个槽位,下标 0..n-1 恰好可以记录值 1..n:
值 1 -> 下标 0
值 2 -> 下标 1
...
值 x -> 下标 x - 1
若有效值 x 出现,就尽量把一个 x 放到 nums[x - 1]。整理完成后,槽位 index 中若不是
index + 1,就说明该正整数没有出现。
这不是完整排序。算法只关心有效值是否进入自己的槽位;非正数、超范围值和多余重复值可以留在任意位置。
原地归位不变量¶
外层处理下标 index 时,只要当前值 x = nums[index] 位于 [1, n],就计算目标槽位 x - 1。
若目标槽位尚未保存 x,交换 nums[index] 与 nums[x - 1]。交换后,值 x 已经进入正确槽位,但当前位置
得到另一个值;这个新值也可能需要归位,因此必须继续使用 while,而不是立即处理下一个下标。
若 nums[x - 1] == x,目标槽位已经记录了值 x。此时继续交换不会产生新状态:
当前值本来就在正确槽位时,无需移动;
当前值是重复副本时,存在性已经由目标槽位记录。
所以该条件既避免无效交换,也防止重复值造成死循环。
每次真正交换都会把一个有效值永久放入自己的槽位。其他不同值具有不同目标槽位;重复的同值又会被停止条件拦截,
因此已经正确的槽位不会被合法交换破坏。成功交换总数最多为 n,两层循环合计仍为线性工作量。
状态演化¶
对 [3, 4, -1, 1]:
当前下标 |
数组状态 |
动作 |
|---|---|---|
0 |
|
值 3 与槽位 2 交换 |
0 |
|
当前值无效,进入下一下标 |
1 |
|
值 4 与槽位 3 交换 |
1 |
|
新值 1 与槽位 0 交换 |
1 |
|
当前值无效,结束归位 |
最终下标 1 没有保存值 2,因此答案为 2。
首个缺口¶
归位结束后,若有效值 x 在原数组中出现过,至少一个副本会进入槽位 x - 1;后续重复副本只会看到该槽位
已经保存 x 后停止。
因此最终从左向右扫描时,第一处 nums[index] != index + 1 就表示值 index + 1 缺失。更小的槽位全部正确,
说明所有更小正整数都存在,所以它就是最小缺失正整数。若所有槽位都正确,说明 1..n 全部出现,返回
n + 1。
代码演进¶
sortAndScan 通过排序恢复正整数顺序,正确但需要 O(n log n) 时间。
recordWithHashSet 改为记录 [1, n] 中每个值是否出现,达到线性时间,代价是线性额外空间。
placeValuesIntoOwnSlots 保留相同的存在性模型,把集合键 x 映射为数组槽位 x - 1。原数组由此成为固定
值域哈希表,同时满足线性时间和常量额外空间,公开入口采用该方法。
复杂度分析¶
排序扫描:时间
O(n log n);当前实现按值传参,额外空间O(n);哈希集合:期望时间
O(n),额外空间O(n);原地归位:每个槽位最多被永久固定一次,归位与最终扫描合计
O(n)时间,额外空间O(1)。