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

LeetCode 41缺失的第一个正数最优解详解在LeetCode的算法题中41. 缺失的第一个正数 是一道典型的“困难”级别题目。它的难点不在于思路有多复杂而在于其对算法效率的严格要求时间复杂度 O(n)空间复杂度 O(1)。本文将带你一步步剖析如何满足这两个苛刻的条件找出数组中缺失的最小正整数。文章目录LeetCode 41缺失的第一个正数最优解详解题目回顾思路分析为什么常规解法不行核心思想原地哈希索引即键算法步骤详解第一步预处理处理非正数第二步交换元素到正确位置第三步扫描并返回结果代码实现Golang复杂度分析总结题目回顾给你一个未排序的整数数组nums请找出其中没有出现的最小正整数。示例输入nums [3,4,-1,1]输出2解释1 在数组中但 2 没有出现。思路分析为什么常规解法不行看到题目我们很容易想到两种最直接的解法但它们的性能都不达标排序法先排序再遍历。时间复杂度为O(n log n)不满足O(n)的要求。哈希表法将所有数字存入哈希集合然后从1开始查找。时间和空间复杂度均为O(n)空间复杂度不满足O(1)的要求。因此我们必须另辟蹊径利用题目给定的数组本身来作为“哈希表”从而避免申请额外的空间。核心思想原地哈希索引即键这个算法的核心思想是将每个正整数x放到它应该在的位置即索引x-1处。这样数组的索引和值之间就建立了一一对应的关系。完成放置后我们只需遍历数组第一个nums[i] ! i1的位置就是缺失的正数i1。为了让这个“放置”过程顺利进行我们需要进行几步预处理和巧妙的交换。算法步骤详解我们以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循环持续交换直到当前位置的元素无法再归位待交换的值必须在有效范围内即nums[i]的值必须介于1到len(nums)之间。大于数组长度的值无法在数组中找到对应的位置。避免死循环如果nums[i]已经在其正确的位置nums[nums[i]-1]上或者目标位置的值已经与nums[i]相等出现重复数字则停止交换i指针右移。模拟交换过程i 0nums[0] 33应该在索引2处。交换nums[0]和nums[2]数组变为[1, 4, 3, 1]。nums[0]变为1继续交换。1应该在索引0处即当前位置无需交换。指针i右移。i 1nums[1] 44应该在索引3处。交换nums[1]和nums[3]数组变为[1, 1, 3, 4]。nums[1]变为1无需交换。指针i右移。i 2nums[2] 3已经在正确位置。指针i右移。i 3nums[3] 4已经在正确位置。遍历结束。最终数组状态[1, 1, 3, 4]第三步扫描并返回结果现在数组已经“就位”。我们再次遍历数组寻找第一个nums[i] ! i1的位置。i 0nums[0] 1正确。i 1nums[1] 1不等于2。因此缺失的第一个正数是2直接返回。如果所有位置都满足nums[i] i1说明1到len(nums)全部存在那么答案就是len(nums)1。代码实现GolangfuncfirstMissingPositive(nums[]int)int{n:len(nums)hasOne:false// 1. 预处理检查1是否存在并将非正数转为1fori:0;in;i{ifnums[i]1{hasOnetrue}elseifnums[i]1{nums[i]1}}if!hasOne{return1}// 2. 原地哈希将每个数字x放到索引x-1处fori:0;in;i{// 持续交换直到当前位置的值无法归位fornums[i]nnums[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;in;i{ifnums[i]!i1{returni1}}returnn1}复杂度分析时间复杂度O(n)。虽然看起来有两层循环但每个元素最多被交换一次因此总的时间复杂度是线性的。空间复杂度O(1)。我们只使用了常数个额外变量所有操作都在原数组上进行。总结这道题的“原地哈希”解法是算法中**“空间换时间”**思想的逆向应用——用时间换空间。它巧妙地将数组本身改造为哈希表在不增加额外存储的前提下利用索引与值的映射关系高效地解决了问题。掌握这种思想对于解决一类“给定数组寻找缺失/重复元素”的问题非常有帮助例如 LeetCode 的第 448 题找到所有数组中消失的数字和 第 287 题寻找重复数都可以用类似思路解决。