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

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

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

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

题目回顾

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

示例：

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

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

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

1. 排序法：先排序，再遍历。时间复杂度为O(n log n)，不满足O(n)的要求。
2. 哈希表法：将所有数字存入哈希集合，然后从1开始查找。时间和空间复杂度均为O(n)，空间复杂度不满足O(1)的要求。

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

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

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

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

算法步骤详解

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

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

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

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

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

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

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

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

1. 待交换的值必须在有效范围内：即nums[i]的值必须介于1到len(nums)之间。大于数组长度的值，无法在数组中找到对应的位置。
2. 避免死循环：如果nums[i]已经在其正确的位置nums[nums[i]-1]上，或者目标位置的值已经与nums[i]相等（出现重复数字），则停止交换，i指针右移。

模拟交换过程：

• 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）

funcfirstMissingPositive(nums[]int)int{n:=len(nums)hasOne:=false// 1. 预处理：检查1是否存在，并将非正数转为1fori:=0;i<n;i++{ifnums[i]==1{hasOne=true}elseifnums[i]<1{nums[i]=1}}if!hasOne{return1}// 2. 原地哈希：将每个数字x放到索引x-1处fori:=0;i<n;i++{// 持续交换，直到当前位置的值无法归位fornums[i]<=n&&nums[i]>0{// 如果目标位置已有正确值，或出现重复，则退出循环ifnums[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. 扫描查找第一个缺失的正数fori:=0;i<n;i++{ifnums[i]!=i+1{returni+1}}returnn+1}

复杂度分析

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

总结

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

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