企业官网建设流程全解析

这次我们来看一个算法训练营的习题——原地哈希。这个题目来自27代码打卡营第八周的第三题，重点不是概念多复杂，而是能不能在实际编码中快速识别适用场景、掌握实现套路。

原地哈希的核心价值在于：它能在O(1)的额外空间复杂度下，解决数组元素与索引映射类问题。如果你正在准备技术面试，或者想提升对数组操作的敏感度，这篇文章会带你完成从问题识别到代码实现的完整闭环。

本文会重点拆解原地哈希的适用场景、实现模板、边界处理，并给出可直接运行的Python代码。我们会通过几个典型例题，让你掌握如何在不使用额外哈希表的情况下，通过数组本身的空间完成元素统计、重复检测或缺失值查找。

1. 原地哈希核心能力速览

原地哈希不是万能的，它最适合元素值范围与数组索引存在天然映射关系的问题。比如数组长度为n，元素值在[1, n]或[0, n-1]范围内时，索引本身就能作为完美的哈希函数。

2. 适用场景与使用边界

原地哈希最适合解决以下几类问题：

重复元素检测：给定长度为n的数组，元素范围在[1, n]之间，找出重复出现的数字。经典例题如LeetCode 287（寻找重复数）。

缺失数字查找：长度为n的数组包含[0, n]或[1, n+1]范围内的数字，找出缺失的那个。比如LeetCode 268（缺失数字）。

第一个缺失正数：在未排序数组中找到最小的缺失正整数。这是LeetCode 41的经典题目，最能体现原地哈希的价值。

使用边界需要注意：

• 数组元素必须能够映射到有效索引，否则需要预处理
• 修改原数组是必要的代价，如果数组不可修改则不能使用
• 适用于单次遍历解决问题的场景，多次随机访问可能不划算

3. 环境准备与前置条件

要实践原地哈希算法，你只需要基础的编程环境：

编程语言：Python 3.6+（本文示例使用Python）开发工具：任意代码编辑器或IDE（VS Code、PyCharm等）运行环境：本地Python解释器或在线编程平台算法基础：了解数组操作、时间复杂度分析

不需要额外的库或框架，原地哈希的核心是算法思维而非工具依赖。

4. 原地哈希实现模板

原地哈希的基本思路是：遍历数组，将每个元素放到它应该在的位置上。如果目标位置已经有正确元素，说明发现重复；如果遍历完成后还有位置不对，说明存在缺失。

下面是通用的Python实现模板：

def in_place_hash(nums): n = len(nums) # 第一遍遍历：将元素放到正确位置 for i in range(n): # 不断交换，直到当前位置的元素是合适的，或者发现重复 while nums[i] != i + 1: # 假设期望是[1, n]映射到索引[0, n-1] target_index = nums[i] - 1 # 如果目标位置已经有正确元素，说明nums[i]是重复的 if nums[target_index] == nums[i]: break # 交换元素到正确位置 nums[i], nums[target_index] = nums[target_index], nums[i] # 第二遍遍历：检查哪个位置不符合预期 for i in range(n): if nums[i] != i + 1: return i + 1 # 返回缺失的数字 return n + 1 # 如果都符合，说明缺失的是n+1

这个模板可以适配多种变体问题，关键调整在于映射关系和终止条件。

5. 典型例题实战解析

5.1 寻找重复数（LeetCode 287）

题目要求：给定包含n+1个整数的数组nums，其数字都在[1, n]范围内，假设只有一个重复的数字，找出这个重复的数。

解题思路：

• 利用索引0到n，对应数字1到n+1
• 遍历数组，将每个数字交换到对应的索引位置
• 如果交换时发现目标位置已经是正确数字，说明找到重复

Python实现：

def findDuplicate(nums): n = len(nums) - 1 # 数字范围是[1, n]，数组长度是n+1 i = 0 while i < len(nums): # 如果当前数字已经在正确位置，或者当前是0（0不在[1,n]范围内） if nums[i] == i + 1 or nums[i] == 0: i += 1 continue target_index = nums[i] - 1 # 如果目标位置已经有相同的数字，说明找到重复 if nums[target_index] == nums[i]: return nums[i] # 交换到正确位置 nums[i], nums[target_index] = nums[target_index], nums[i] return -1 # 理论上不会执行到这里 # 测试用例 test_nums = [1, 3, 4, 2, 2] print(findDuplicate(test_nums)) # 输出: 2

关键点：

• 注意数组长度是n+1，数字范围是[1, n]
• 交换时要检查目标位置是否已经是正确数字
• 时间复杂度O(n)，空间复杂度O(1)

5.2 第一个缺失的正数（LeetCode 41）

这是原地哈希最经典的应用场景：给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。

解题思路：

• 将数组视为哈希表，数字x应该出现在索引x-1的位置
• 遍历数组，将每个正整数放到正确位置
• 再次遍历，第一个位置不匹配的就是答案

Python实现：

def firstMissingPositive(nums): n = len(nums) # 第一遍：将正整数放到正确位置 for i in range(n): # 不断交换，直到当前元素不在[1, n]范围内，或者已经在正确位置 while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: # 交换到正确位置 correct_index = nums[i] - 1 nums[i], nums[correct_index] = nums[correct_index], nums[i] # 第二遍：查找第一个位置不匹配的 for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1 # 测试用例 test_cases = [ [1, 2, 0], # 期望输出: 3 [3, 4, -1, 1], # 期望输出: 2 [7, 8, 9, 11, 12] # 期望输出: 1 ] for nums in test_cases: print(f"输入: {nums}, 输出: {firstMissingPositive(nums[:])}") # 使用[:]避免修改原数组

算法分析：

• 时间复杂度：每个元素最多被交换一次，O(n)
• 空间复杂度：只使用了常数额外空间，O(1)
• 关键技巧：while循环确保元素被放到正确位置

5.3 缺失数字（LeetCode 268）

给定包含[0, n]中n个数的数组nums，找出[0, n]范围内没有出现在数组中的那个数。

解题思路：

• 数字范围[0, n]正好对应索引[0, n]
• 将每个数字放到对应索引位置
• 遍历检查哪个索引位置的值不等于索引

Python实现：

def missingNumber(nums): n = len(nums) # 第一遍：将数字放到正确位置 for i in range(n): # 当前位置的数字可能大于n（因为缺失一个数，所以有一个位置是n） while nums[i] != i and nums[i] < n: correct_index = nums[i] nums[i], nums[correct_index] = nums[correct_index], nums[i] # 第二遍：查找缺失的数字 for i in range(n): if nums[i] != i: return i return n # 如果0到n-1都正确，说明缺失的是n # 测试用例 test_cases = [ [3, 0, 1], # 期望输出: 2 [0, 1], # 期望输出: 2 [9,6,4,2,3,5,7,0,1] # 期望输出: 8 ] for nums in test_cases: print(f"输入: {nums}, 输出: {missingNumber(nums[:])}")

6. 原地哈希的变体与优化

6.1 标记法原地哈希

对于不能修改数组元素值的情况，可以使用标记法。基本原理是通过正负号来记录某个数字是否出现过。

def firstMissingPositiveMark(nums): n = len(nums) # 第一遍：将非正数标记为n+1（超出范围） for i in range(n): if nums[i] <= 0: nums[i] = n + 1 # 第二遍：将出现过的数字对应位置标记为负数 for i in range(n): num = abs(nums[i]) if num <= n: nums[num - 1] = -abs(nums[num - 1]) # 第三遍：找到第一个正数位置 for i in range(n): if nums[i] > 0: return i + 1 return n + 1

6.2 循环排序模式

循环排序是原地哈希的一种系统化实现，特别适合元素范围已知的排序问题。

def cyclicSort(nums): n = len(nums) i = 0 while i < n: correct_index = nums[i] - 1 # 假设范围是[1, n] # 如果当前元素不在正确位置，交换 if nums[i] != nums[correct_index]: nums[i], nums[correct_index] = nums[correct_index], nums[i] else: i += 1 return nums # 测试循环排序 test_nums = [3, 1, 5, 4, 2] print("排序前:", test_nums) print("排序后:", cyclicSort(test_nums))

7. 性能分析与优化技巧

7.1 时间复杂度分析

原地哈希算法通常包含两个循环：

• 第一个循环：放置元素到正确位置，每个元素最多被交换一次，O(n)
• 第二个循环：检查结果，O(n)
• 总体时间复杂度：O(n)

7.2 空间复杂度优势

与传统哈希表相比的优势：

• 哈希表：O(n)额外空间
• 原地哈希：O(1)额外空间
• 在内存受限环境中优势明显

7.3 优化技巧

提前终止：如果在放置过程中已经发现问题答案，可以提前返回。

边界处理优化：对于超出范围的元素，可以在第一轮遍历中集中处理。

交换次数优化：确保每次交换都让至少一个元素到达正确位置。

8. 常见问题与排查方法

8.1 典型错误示例

# 错误示例：缺少边界检查 def wrongInPlaceHash(nums): n = len(nums) for i in range(n): # 可能越界：如果nums[i]很大 while nums[i] != i + 1: target_index = nums[i] - 1 # 可能越界 nums[i], nums[target_index] = nums[target_index], nums[i] # ... 后续检查逻辑

修正方法：

def correctInPlaceHash(nums): n = len(nums) for i in range(n): # 添加范围检查 while 1 <= nums[i] <= n and nums[i] != i + 1: target_index = nums[i] - 1 # 避免重复交换 if nums[target_index] != nums[i]: nums[i], nums[target_index] = nums[target_index], nums[i] else: break # ... 后续检查逻辑

9. 最佳实践与使用建议

9.1 适用场景判断

在遇到数组问题时，先问自己这几个问题：

1. 元素范围是否已知？如果数字范围在[1, n]或[0, n-1]之间，优先考虑原地哈希。

2. 是否允许修改原数组？原地哈希必须修改数组，如果要求保持原数组不变，需要先复制。

3. 空间限制是否严格？如果要求O(1)空间复杂度，原地哈希是理想选择。

9.2 编码实践建议

模板化开发：掌握基本模板，根据具体问题调整映射关系。

测试用例设计：覆盖边界情况，如空数组、单个元素、完全有序、完全逆序等。

逐步验证：先在小规模数据上验证逻辑正确性，再处理大规模数据。

9.3 面试应用技巧

沟通思路：先说明选择原地哈希的原因（空间复杂度优势）。

手写代码：熟练掌握模板，能够快速写出无bug的实现。

复杂度分析：清晰说明时间复杂度和空间复杂度。

原地哈希是面试中常见的高频考点，特别是LeetCode 41（第一个缺失的正数）和287（寻找重复数）。掌握这个技巧，能在很多数组相关问题中给出最优解。

10. 总结与下一步

原地哈希的核心价值在于用索引本身作为哈希函数，在O(1)空间内解决数组统计问题。最关键的是识别适用场景——当元素范围与索引范围存在天然映射时，这就是最佳选择。

建议从LeetCode 41开始练习，这是最经典的原地哈希应用题。掌握后可以扩展到268、287、448等相似问题。在实际编码中，注意边界处理和终止条件，避免无限循环。

下一步可以学习更多空间换时间的技巧，比如位运算、快慢指针等，这些方法与原地哈希结合使用，能解决更复杂的数组问题。