一天一道算法题（8）：原地哈希的思路与实现解析

LeetCode 41：缺失的第一个正数（最优解详解）

在LeetCode的算法题中，41. 缺失的第一个正数 是一道典型的“困难”级别题目。它的难点不在于思路有多复杂，而在于其对算法效率的严格要求：时间复杂度 O(n)，空间复杂度 O(1)。

本文将带你一步步剖析，如何满足这两个苛刻的条件，找出数组中缺失的最小正整数。

文章目录

• • LeetCode 41：缺失的第一个正数（最优解详解）
  • • 题目回顾
    • 思路分析：为什么常规解法不行？
    • 核心思想：原地哈希（索引即键）
    • 算法步骤详解
    • • 第一步：预处理（处理非正数）
      • 第二步：交换元素到正确位置
      • 第三步：扫描并返回结果
    • 代码实现（Golang）
    • 复杂度分析
    • 总结

题目回顾

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

示例：

输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有出现。

思路分析：为什么常规解法不行？

看到题目，我们很容易想到两种最直接的解法，但它们的性能都不达标：

因此，我们必须另辟蹊径，利用题目给定的数组本身来作为“哈希表”，从而避免申请额外的空间。

核心思想：原地哈希（索引即键）

这个算法的核心思想是：将每个正整数 x 放到它应该在的位置，即索引 x-1 处。 这样，数组的索引和值之间就建立了一一对应的关系。完成放置后，我们只需遍历数组，第一个 nums[i] != i+1 的位置，就是缺失的正数 i+1。

为了让这个“放置”过程顺利进行，我们需要进行几步预处理和巧妙的交换。

算法步骤详解

我们以 nums = [3, 4, -1, 1] 为例，来走一遍完整的流程。

第一步：预处理（处理非正数）

• 目标：统一处理非正数，避免它们在后续交换中干扰索引。
• 逻辑：
• 首先，检查数组中是否存在 1。如果不存在，直接返回 1，因为 1 就是缺失的最小正数。
• 如果存在 1，我们将数组中所有 <= 0 的数字都修改为 1。这样，数组中的所有元素都变成了正数，方便后续操作。

为何要改为 1？ 因为我们只关心正数，将非正数改为 1 既不会丢失有用信息（1 已经存在），又能防止它们参与交换时导致索引越界或逻辑混乱。

操作后： [3, 4, -1, 1] 变为 [3, 4, 1, 1]。

第二步：交换元素到正确位置

这是算法的核心步骤。我们用一个指针 i 从左向右遍历数组。对于每个位置 i，我们希望通过交换，让 nums[i] 这个值去到它“应该在”的索引 nums[i]-1 处。

交换过程遵循以下规则（使用for循环持续交换，直到当前位置的元素无法再归位）：

模拟交换过程：

• i = 0，nums[0] = 3：3 应该在索引 2 处。 交换 nums[0] 和 nums[2]，数组变为 [1, 4, 3, 1]。 nums[0] 变为 1，继续交换。1 应该在索引 0 处，即当前位置，无需交换。指针 i 右移。

• i = 1，nums[1] = 4：4 应该在索引 3 处。 交换 nums[1] 和 nums[3]，数组变为 [1, 1, 3, 4]。 nums[1] 变为 1，无需交换。指针 i 右移。

• i = 2，nums[2] = 3：已经在正确位置。指针 i 右移。

• i = 3，nums[3] = 4：已经在正确位置。遍历结束。

最终数组状态： [1, 1, 3, 4]

第三步：扫描并返回结果

现在，数组已经“就位”。我们再次遍历数组，寻找第一个 nums[i] != i+1 的位置。

• i = 0，nums[0] == 1，正确。
• i = 1，nums[1] == 1，不等于 2。

因此，缺失的第一个正数是 2，直接返回。

如果所有位置都满足 nums[i] == i+1，说明 1 到 len(nums) 全部存在，那么答案就是 len(nums)+1。

代码实现（Golang）

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

// 1. 预处理：检查1是否存在，并将非正数转为1
for i := 0; i < n; i++ {
if nums[i] == 1 {
hasOne = true
} else if nums[i] < 1 {
nums[i] = 1
}
}
if !hasOne {
return 1
}

// 2. 原地哈希：将每个数字x放到索引x-1处
for i := 0; i < n; i++ {
// 持续交换，直到当前位置的值无法归位
for nums[i] <= n && nums[i] > 0 {
// 如果目标位置已有正确值，或出现重复，则退出循环
if nums[i] == nums[nums[i]–1] {
break
}
// 交换 nums[i] 和 nums[nums[i]-1]
nums[i], nums[nums[i]–1] = nums[nums[i]–1], nums[i]
}
}

// 3. 扫描查找第一个缺失的正数
for i := 0; i < n; i++ {
if nums[i] != i+1 {
return i + 1
}
}
return n + 1
}

复杂度分析

• 时间复杂度： O(n)。虽然看起来有两层循环，但每个元素最多被交换一次，因此总的时间复杂度是线性的。
• 空间复杂度： O(1)。我们只使用了常数个额外变量，所有操作都在原数组上进行。

总结

这道题的“原地哈希”解法，是算法中**“空间换时间”**思想的逆向应用——用时间换空间。它巧妙地将数组本身改造为哈希表，在不增加额外存储的前提下，利用索引与值的映射关系，高效地解决了问题。

掌握这种思想，对于解决一类“给定数组，寻找缺失/重复元素”的问题非常有帮助，例如 LeetCode 的第 448 题（找到所有数组中消失的数字）和 第 287 题（寻找重复数）都可以用类似思路解决。