0041. First Missing Positive
============================
题目信息
--------
:题号: 0041. 缺失的第一个正数
:难度: Hard
:主题: 数组、哈希集合、原地哈希、循环置换
:原题: `LeetCode 0041 `_
:重点: 从记录正整数是否出现,推导到用数组下标充当值域槽位,并在线性时间内完成原地归位
题目重述
--------
给定一个未排序整数数组 ``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++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
int sortAndScan(std::vector 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& nums) {
std::unordered_set present;
const int n = static_cast(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& nums) {
const int n = static_cast(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& 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``:
.. code-block:: text
值 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]``:
.. list-table::
:header-rows: 1
* - 当前下标
- 数组状态
- 动作
* - 0
- ``[3, 4, -1, 1]``
- 值 3 与槽位 2 交换
* - 0
- ``[-1, 4, 3, 1]``
- 当前值无效,进入下一下标
* - 1
- ``[-1, 4, 3, 1]``
- 值 4 与槽位 3 交换
* - 1
- ``[-1, 1, 3, 4]``
- 新值 1 与槽位 0 交换
* - 1
- ``[1, -1, 3, 4]``
- 当前值无效,结束归位
最终下标 ``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)``。