First Missing Positive

困难数组和字符串哈希

+10

给你一个未排序的整数数组 nums。返回 nums 中没有出现的最小正整数（大于或等于 1）。数组中可能包含负数、零、重复值，以及远大于数组长度的值。

函数

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: 未排序的整数，这些整数可能重复，也可能是负数、零或非常大的数
返回值integer: nums 中缺失的最小正整数

约束条件

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
这些值没有特定顺序，也可能重复。

示例

输入: nums = [5, -2, 1, 3, 2, 9]
输出: 4
解释: 1、2 和 3 都在数组中，而 4 不在，所以答案是 4。只要缺少一个更小的值，5 和 9 就不重要了。

进阶

你能否只使用 O(n) 时间和 O(1) 额外空间找到答案？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

排序需要 O(n log n) 时间，哈希集合需要 O(n) 额外内存。利用一个上界可以同时优于这两种方法：n 个值最多覆盖 1 到 n+1 之间的 n 个数字，因此答案最多为 n+1。只有 1 到 n 之间的值才有意义，而数组有 n 个位置来记录它们，因此额外内存降为 O(1)。

对每个候选项进行完整扫描

结果正确，但无法在最大的测试中运行完毕

思路

按顺序测试候选数 1、2、3、……。对每个候选数，扫描整个数组，并返回扫描时未找到的第一个候选数。根据上界，你不会测试到 n+1 之后。

当数组包含 1 到 n 时，平均每个候选数都会在扫描到一半时被找到，因此 n = 10^4 时，开销约为 n²/2 = 5 × 10^7 次比较。

算法

将 candidate 设为 1。
扫描 nums，查找等于 candidate 的元素，找到第一个后停止。
如果没有匹配的元素，则返回 candidate。
否则，将 candidate 加 1，然后再次扫描。你不会超过 n+1。

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

在标记数组中标记从 1 到 n 的值

思路

由于答案最多为 n+1，因此跳过小于 1 或大于 n 的值。长度为 n+1 的布尔数组 present 用来记录其余值，因此不会存储像 10^9 这样的值。返回从 1 到 n 中第一个标记为 false 的 v；如果所有标记都已设置，则返回 n+1。

在第一个示例中，n = 6：1、2、3 和 5 对应的标记会被设置，-2 和 9 会被跳过，第一个未设置的标记是 4。两次线性遍历的时间复杂度为 O(n)，标记占用 O(n) 的内存。

算法

创建 present，其中有 n+1 个标记，初始值都为 false。
对于 nums 中满足 1 ≤ v ≤ n 的每个值 v，将 present[v] 设为 true。
返回从 1 到 n 中第一个标记为 false 的 v。
如果没有这样的值，则返回 n+1。

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

将每个值放入各自的槽位

思路

值 v 应位于索引 v-1。当从 1 到 n 的每个值都在各自的位置上时，第一个没有存放 i+1 的索引 i 就表示答案。

遍历每个索引，只要值在 1 到 n 之间，且它应在的位置还没有这个值，就把它换到应在的位置。换回来的值也可能需要移动。检查值应在的位置，而不是检查 i，可以避免重复值导致问题：在 [1, 1] 中，第二个 1 会发现索引 0 处已经是 1，于是保持不动。

在第一个示例中，索引 0 先把 5 放回应在的位置，然后把换回来的 2 放回去；之后，1 和 3 也各自归位，留下 [1, 2, 3, -2, 5, 9]：索引 3 是第一个位置错误的槽位，所以答案是 4。

每次交换都会让一个值永久归位，因此内层循环总共最多进行 n 次交换：时间复杂度为 O(n)，空间复杂度为 O(1)，但 R 除外，因为它会复制被修改的向量。

算法

对于从 0 到 n-1 的每个索引 i：
当 1 ≤ nums[i] ≤ n 且 nums[nums[i]-1] ≠ nums[i] 时，将 nums[i] 与 nums[nums[i]-1] 交换。
放置完成后，找到第一个满足 nums[i] ≠ i+1 的索引 i，并返回 i+1。
如果每个位置都存放着对应的值，则返回 n+1。

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

易错点和边界情况

在 nums[i] == i+1 时停止交换，而不是在目标位置已经存放正确的值时停止。对于 [1, 1]，两个 1 会一直交换。
使用 if 而不是 while 进行交换。在第一个示例中，从索引 4 回到的 2 永远到不了索引 1，因此你会返回 2，而不是 4。
先写入 nums[i] = nums[nums[i]-1]，然后再次用 nums[i] 进行索引，这会在值改变后读取目标索引。请先保存目标索引。
跳过范围检查，会导致 0、-2 或 10^9 被用作数组范围外的索引。
所有位置都正确时返回 n。对于 [4, 2, 1, 3]，答案是 5。

常见问题3

First Missing Positive 的时间复杂度是多少？

置放方案的时间复杂度为 O(n)，额外空间复杂度为 O(1)。while 循环位于 for 循环内，但每次交换都会将一个值放到最终索引处，因此整个运行过程最多进行 n 次交换。使用标记数组的版本时间复杂度为 O(n)，空间复杂度为 O(n)；而对每个候选值进行扫描的时间复杂度为 O(n²)。

为什么答案永远不会大于 n+1？

从 1 到 n+1 的数字共有 n+1 个，且数组长度为 n，最多只能包含 n 个不同的值，因此其中一个值缺失。只有当数组包含从 1 到 n 的每个值时，答案才是 n+1。

原地解决方案会改变输入数组吗？

是的，它会重新排列这些值。如果调用方需要保留原来的顺序，请先复制数组，这样额外内存就会回到 O(n)。另一种原地方法会把所有小于 1 或大于 n 的值替换为 n+1，然后通过将 nums[v-1] 变为负数来标记 v 存在；这种方法也会改变数组。

def firstMissingPositive(nums):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

nums = [5, -2, 1, 3, 2, 9]

预期输出