LeetCode 41 - 缺失的第一个正数（First Missing Positive）

问题描述

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

示例 1：

1 2	输入：nums = [1,2,0] 输出：3

示例 2：

1 2	输入：nums = [3,4,-1,1] 输出：2

示例 3：

1 2	输入：nums = [7,8,9,11,12] 输出：1

约束条件：

1 <= nums.length <= 5 * 10^5
-2^31 <= nums[i] <= 2^31 - 1

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

解题思路

这道题的关键在于理解一个重要的性质：如果长度为 n 的数组包含所有 1 到 n 的数字，那么缺失的第一个正数就是 n+1。如果存在缺失，那么答案一定在 1 到 n+1 之间。

基于这个性质，我们可以利用数组本身作为哈希表，实现原地哈希。思路是将值 x 放到索引 x-1 的位置，这样当我们再次遍历数组时，第一个不满足 nums[i] == i+1 的位置就是缺失的第一个正数。

原地哈希的核心思想

假设我们有一个完美的数组，其中：

nums[0] = 1
nums[1] = 2
nums[2] = 3
...
nums[i] = i+1

这样的数组中，每个正数都在"家"（正确的位置）。对于值 x，它的"家"是索引 x-1。

当数组中有缺失的正数时，我们就能通过查找哪个位置上的数不是"应该在那里的数"来找到答案。

算法步骤：

原地哈希排序：
- 遍历数组，将每个在 [1, n] 范围内的数放到其对应的位置
- 对于每个元素 nums[i]，如果 1 ≤ nums[i] ≤ n 并且 nums[i] ≠ nums[nums[i]-1]，则交换 nums[i] 和 nums[nums[i]-1]
- 继续检查交换后的 nums[i]，直到不需要交换为止
查找缺失的最小正数：
- 再次遍历数组，找到第一个不满足 nums[i] = i+1 的位置
- 该位置的索引 +1 就是答案

图示说明

对于数组 [3,4,-1,1]，原地哈希过程：

初始状态: [ 3, 4, -1, 1]
↓
排序过程: [-1, 1, 3, 4]
↓ ↓
最终状态: [ 1, -1, 3, 4]
↓
缺失的是 2

代码实现

func firstMissingPositive(nums []int) int {
    n := len(nums)

    // 第一阶段：将每个数放到正确的位置
    for i := 0; i < n; i++ {
        // nums[i] 应该放在索引 nums[i]-1 的位置
        // 只处理在 [1,n] 范围内的值，且目标位置没有正确的值
        for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            // 交换 nums[i] 和 nums[nums[i]-1]
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }

    // 第二阶段：找出第一个不满足 nums[i] == i+1 的位置
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }

    // 如果数组包含了 1 到 n 的所有数，则缺失的第一个正数是 n+1
    return n + 1
}

执行过程分析

以数组 [3, 4, -1, 1] 为例，详细分析执行过程：

第一阶段：原地哈希排序

i=0, nums[0]=3
- 3 应该在索引 2 的位置
- 交换 nums[0] 和 nums[2]：[3, 4, -1, 1] → [-1, 4, 3, 1]
i=0, nums[0]=-1
- -1 不在范围 [1, n] 内，跳过
i=1, nums[1]=4
- 4 应该在索引 3 的位置
- 交换 nums[1] 和 nums[3]：[-1, 4, 3, 1] → [-1, 1, 3, 4]
i=1, nums[1]=1
- 1 应该在索引 0 的位置
- 交换 nums[1] 和 nums[0]：[-1, 1, 3, 4] → [1, -1, 3, 4]
i=1, nums[1]=-1
- -1 不在范围 [1, n] 内，跳过
i=2, nums[2]=3
- 3 已经在正确的位置（索引 2），跳过
i=3, nums[3]=4
- 4 已经在正确的位置（索引 3），跳过

排序完成后的数组：[1, -1, 3, 4]

第二阶段：查找缺失的最小正数

i=0, nums[0]=1 == 0+1 ✓
i=1, nums[1]=-1 != 1+1 ✗

找到了第一个不满足条件的位置 i=1，因此答案是 1+1 = 2。

复杂度分析

时间复杂度：O(n)
- 虽然有嵌套循环，但每个元素最多被交换一次到正确位置，一旦到达正确位置就不会再移动
- 第二次遍历是线性的 O(n)
空间复杂度：O(1)
- 原地修改数组，不使用额外空间

常见错误与优化

死循环问题：
- 在内层循环的交换条件中，必须包含 nums[nums[i]-1] != nums[i]
- 否则当 nums[i] 等于 nums[nums[i]-1] 时会陷入无限交换的死循环
提前返回问题：
- 不能在第一阶段结束前判断结果，必须完成整个排序过程
- 因为数组可能还没有完全排好序
边界处理：
- 注意处理负数和超出数组长度的值，它们不需要参与交换

总结

缺失的第一个正数问题是一个经典的原地哈希问题。关键洞察在于：对于长度为 n 的数组，答案一定在 1 到 n+1 之间，这使得我们可以利用数组本身作为哈希表，将值 x 放在索引 x-1 的位置上。

这种方法的精妙之处在于它既满足了 O(n) 的时间复杂度要求，又满足了 O(1) 的空间复杂度要求。它展示了如何通过巧妙地利用问题约束来设计高效算法的思想。

Adrian Wang's blog