当前位置：首页 > news >正文

LeetCode 41题实战：用‘原地哈希’在O(n)时间内找出缺失的最小正整数（附C++/Python代码）

news 2026/5/15 20:12:42

LeetCode 41题深度解析：原地哈希算法在缺失最小正整数问题中的精妙应用

引言

算法面试中，原地哈希（In-place Hashing）是一种常被忽视却极其强大的技巧。当面对LeetCode第41题"缺失的第一个正数"时，大多数求职者会陷入排序或哈希表的常规思路，却忽略了题目对时间复杂度和空间复杂度的严苛要求。这道题之所以被标记为"Hard"，不仅因为其思维难度，更因为它完美展现了如何用基础操作解决复杂问题的艺术。

本文将带你从问题本质出发，逐步拆解原地哈希的核心思想，揭示其在空间优化中的独特价值。不同于简单的代码实现，我们会深入探讨算法设计背后的逻辑链条：为什么常规方法失效？原地哈希如何巧妙地利用现有空间？如何处理负数、大数和重复值的边界情况？通过完整的思路构建、代码实现和面试技巧，你将掌握一种适用于多类约束性问题的通用解法。

1. 问题分析与常规解法局限

给定一个未排序的整数数组，找出其中没有出现的最小正整数。题目要求时间复杂度O(n)且只能使用常数额外空间。让我们先看几个示例：

[1,2,0] → 3
[3,4,-1,1] → 2
[7,8,9,11,12] → 1

直观解法及其问题：

暴力枚举法：从1开始逐个检查是否存在于数组中。时间复杂度O(n²)，空间O(1)
```
def firstMissingPositive(nums): for i in range(1, len(nums)+2): if i not in nums: return i
```

排序法：先排序再线性扫描。时间复杂度O(nlogn)，空间取决于排序实现

def firstMissingPositive(nums): nums.sort() res = 1 for num in nums: if num == res: res += 1 return res

哈希表法：使用集合存储数字，然后检查1到n+1。时间O(n)，空间O(n)

def firstMissingPositive(nums): num_set = set(nums) for i in range(1, len(nums)+2): if i not in num_set: return i

关键观察：这些方法要么时间不达标，要么空间不符合要求。我们需要一种能利用数组自身结构的解法。

2. 原地哈希的核心思想

原地哈希的精髓在于将数组索引本身作为哈希键。对于长度为n的数组，缺失的最小正整数必然在[1, n+1]范围内。我们可以重新排列数组，使得数字i出现在索引i-1的位置（即1在0位，2在1位...）。

算法步骤：

遍历数组，将每个数字x交换到x-1的位置
忽略x ≤ 0或x > n的情况（它们不影响最小正整数的判断）
处理完成后，第一个不满足nums[i] == i+1的位置即为答案

C++实现核心逻辑：

for(int i=0; i<nums.size(); ++i){ while(nums[i]>0 && nums[i]<=nums.size() && nums[nums[i]-1]!=nums[i]){ swap(nums[i], nums[nums[i]-1]); } }

为什么时间复杂度是O(n)？每个数字最多被交换一次到正确位置，尽管有嵌套循环，但总操作次数与数组长度成线性关系。

3. 边界条件与特殊处理

3.1 处理重复元素

当遇到重复数字时，直接跳过避免无限循环：

while 0 < nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]: nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]

3.2 大数和负数的影响

数字>n：不影响最小正整数的判断（缺失数≤n+1）
数字≤0：同样忽略，因为它们不参与正整数序列

Python完整实现：

def firstMissingPositive(nums): n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]: nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] for i in range(n): if nums[i] != i+1: return i+1 return n+1

3.3 置换环理论解析

原地哈希本质上是将数组分解为多个置换环。每个环中的元素通过交换达到正确位置：

示例数组：[3,4,-1,1] 置换过程： - 3应该到位置2 → 交换3和-1 → [-1,4,3,1] - -1跳过 - 4应该到位置3 → 交换4和1 → [-1,1,3,4] - 1应该到位置0 → 交换1和-1 → [1,-1,3,4] 最终检查发现位置1不是2，返回2

4. 面试实战技巧与变体问题

4.1 面试常见考察点

复杂度分析：如何证明时间复杂度是O(n)而非O(n²)
边界测试：
- 空数组应返回1
- 全负数数组应返回1
- 包含重复元素的数组如[1,1]应返回2
代码健壮性：
- 检查输入是否为null
- 处理超大数组时的性能考虑

4.2 面试官可能追问的问题

如果允许O(n)空间，你会如何优化解法？
如何修改算法使其同时找出所有缺失的正整数？
如果数组是只读的（不可修改），如何解决？（使用位图或二分法）

4.3 性能对比表格

方法	时间复杂度	空间复杂度	适用场景
暴力枚举	O(n²)	O(1)	小规模数据
排序+扫描	O(nlogn)	O(1)或O(n)	无空间限制
哈希集合	O(n)	O(n)	时间敏感
原地哈希	O(n)	O(1)	严格空间限制