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

LeetCode 41题实战原地哈希算法在O(n)时间找出缺失的最小正整数刷算法题时我们常常会遇到一类经典问题在给定的整数数组中找出缺失的最小正整数。这类问题看似简单但要在O(n)时间内且不使用额外空间解决就需要一些巧妙的技巧。今天我们就来深入探讨LeetCode第41题缺失的第一个正数并重点解析原地哈希这一精妙解法。1. 问题理解与初步分析给定一个未排序的整数数组找出其中没有出现的最小的正整数。要求算法的时间复杂度为O(n)并且只能使用常数级别的额外空间。举个例子输入[3,4,-1,1]输出2解释数组中包含1、3、4但缺少2关键约束条件时间复杂度O(n)空间复杂度O(1)数组可能包含负数和重复值数组长度可能很大提示面试中遇到这类问题首先要明确问题的边界条件和约束这是解题的第一步。2. 原地哈希算法原理原地哈希(In-place Hashing)是一种在不使用额外空间的情况下利用输入数组本身作为哈希表的技术。其核心思想是通过重新排列数组元素使得每个元素的值与其索引之间存在某种对应关系。对于本题我们可以利用以下观察缺失的最小正整数一定在1到n1之间n为数组长度我们可以将数组视为哈希表通过交换元素使得nums[i] i1算法步骤概述遍历数组将每个正整数x放到它应该在的位置即索引x-1处再次遍历数组第一个不满足nums[i] i1的位置i对应的i1就是缺失的最小正整数如果所有位置都满足条件则缺失的是n13. 详细实现步骤与边界处理让我们用C和Python分别实现这个算法并详细讨论各种边界情况的处理。3.1 C实现int firstMissingPositive(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { while (nums[i] 0 nums[i] n nums[nums[i]-1] ! nums[i]) { swap(nums[i], nums[nums[i]-1]); } } for (int i 0; i n; i) { if (nums[i] ! i1) { return i1; } } return n1; }关键点解析使用while循环而不是if确保交换后的新元素也被正确处理交换条件nums[nums[i]-1] ! nums[i]避免无限循环处理完所有元素后只需线性扫描找出第一个不匹配的位置3.2 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 1Python实现特点利用Python的多重赋值特性简化交换操作条件判断更加简洁直观整体结构与C版本高度一致3.3 边界情况处理在实际编码中我们需要特别注意以下几种边界情况边界情况处理方法示例输入预期输出包含负数跳过不处理[-1, -2, 0]1包含重复值避免无限循环[1, 1]2所有数都连续返回n1[1, 2, 3]4空数组直接返回1[]14. 算法复杂度分析让我们从时间和空间两个维度分析这个算法的性能时间复杂度表面看有两层循环但每个元素最多被交换一次到正确位置因此总体时间复杂度是O(n)空间复杂度只使用了常数级别的额外空间几个临时变量满足O(1)的要求性能对比表方法时间复杂度空间复杂度适用场景排序后扫描O(nlogn)O(1)无空间限制哈希表O(n)O(n)可接受额外空间原地哈希O(n)O(1)严格空间限制5. 面试技巧与常见问题在技术面试中这类问题常常被用来考察候选人对基础算法的理解和编码能力。以下是一些实用的面试技巧先沟通再编码不要直接开始写代码先和面试官确认问题细节和约束条件举例说明用具体例子解释你的思路这有助于面试官理解你的思考过程考虑边界主动讨论各种边界情况展示你的全面思考代码风格写出清晰、模块化的代码适当添加注释常见面试问题如何证明这个算法是正确的为什么使用while循环而不是if如果数组中有重复元素会怎样这个算法能否处理非常大的数组6. 实际应用与扩展原地哈希算法不仅适用于这道LeetCode题目它在许多其他场景也有广泛应用寻找重复元素如LeetCode 287题寻找重复数数组重排列如将数组排序为波浪形缺失多个数字扩展问题找出所有缺失的数字进阶挑战尝试修改算法使其能找出前k个缺失的正整数思考如何在不修改原数组的情况下解决问题虽然会增加空间复杂度研究其他使用原地算法的经典问题如Dutch National Flag问题在实际工程项目中这类算法思想也有其用武之地特别是在内存受限的嵌入式系统或处理大规模数据时原地算法能显著减少内存开销。