1. 问题背景与核心挑战缺失的第一个正数First Missing Positive是算法面试中的经典问题题目要求给定一个未排序的整数数组找出其中没有出现的最小的正整数。这个看似简单的问题却暗藏玄机它考察的不仅是基础编码能力更是对时间/空间复杂度优化的深刻理解。问题的难点在于时间复杂度必须控制在O(n)空间复杂度理想情况下应为O(1)需要处理包含负数和重复值的特殊情况边界条件复杂如空数组、全负数数组等提示面试中遇到这个问题时面试官最期待看到的不是暴力解法而是能否想到原地哈希in-place hashing这种巧妙思路。2. 暴力解法与优化思路2.1 直观的暴力解法最直接的思路是从1开始逐个检查正整数对每个数字遍历整个数组第一个找不到的数字即为答案def firstMissingPositive(nums): i 1 while True: if i not in nums: return i i 1这个解法虽然简单但时间复杂度为O(n²)空间复杂度O(1)显然不符合题目要求。2.2 哈希表优化引入哈希表存储出现过的数字def firstMissingPositive(nums): num_set set(nums) i 1 while i in num_set: i 1 return i时间复杂度降至O(n)但空间复杂度也变成O(n)仍然不是最优解。2.3 原地哈希的突破真正的突破在于意识到长度为n的数组缺失的第一个正数必然在[1, n1]范围内。这个关键观察让我们可以在原数组上通过交换元素来实现哈希遍历数组将每个数字x交换到索引x-1的位置再次遍历第一个不满足nums[i] i1的位置就是答案3. 原地哈希的完整实现3.1 算法步骤详解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 13.2 关键操作解析核心的while循环完成了三件事检查当前数字是否在有效范围内1 ≤ x ≤ n检查目标位置是否已经存放了正确的值通过交换将当前数字放到它应该在的位置这个交换过程看似简单但实际时间复杂度分析很精妙虽然有两层循环但每个数字最多被交换一次所以总体仍是O(n)时间复杂度。4. 边界条件与特殊测试用例4.1 常见边界情况需要特别注意的测试用例包括空数组 → 应返回1全负数数组 → 应返回1包含重复值的数组已经包含1到n的完整数组 → 应返回n1单个元素数组如[1]或[2]4.2 调试技巧在实现过程中建议使用以下测试用例逐步验证test_cases [ ([1,2,0], 3), ([3,4,-1,1], 2), ([7,8,9,11,12], 1), ([], 1), ([1], 2), ([1,1], 2), ([2,2], 1) ]5. 算法优化与变种问题5.1 空间复杂度优化如果允许修改原数组原地哈希是最佳方案。如果不允许修改可以采用位图法用常数空间存储出现标记def firstMissingPositive(nums): # 使用符号位作为标记 n len(nums) # 处理非正数 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 15.2 相关变种问题缺失的第一个非负数允许0缺失的第二个正数在数据流中实时计算缺失的最小正数分布式环境下处理超大数组6. 实际应用场景这个问题虽然抽象但其核心思想在以下场景有实际应用数据库系统中的空闲ID分配内存管理中的页框分配分布式系统中的节点ID分配票务系统的座位分配算法7. 面试中的考察重点面试官通常会从以下几个维度评估候选人的表现能否快速理解问题并给出暴力解法能否发现暴力解法的问题并提出优化思路能否想到原地哈希这种非常规解法代码实现是否考虑各种边界条件能否正确分析算法复杂度8. 个人实现经验分享在实际编码中最容易出错的是交换逻辑的实现。我曾踩过两个坑交换顺序错误导致无限循环# 错误写法 nums[i], nums[nums[i] - 1] nums[nums[i] - 1], nums[i]应该先计算nums[i] - 1再交换。忽略重复元素处理 当数组中有重复元素时需要添加nums[nums[i] - 1] ! nums[i]的判断否则会陷入死循环。另一个实用技巧是在面试中可以先写出哈希表解法然后分析其空间复杂度再自然过渡到原地哈希的优化思路这样展示的思考过程更完整。 
长河君 · 2026/10/28 4:54:04 · 阅读 1.2k 原地哈希算法：高效解决缺失的第一个正数问题
1. 问题背景与核心挑战缺失的第一个正数First Missing Positive是算法面试中的经典问题题目要求给定一个未排序的整数数组找出其中没有出现的最小的正整数。这个看似简单的问题却暗藏玄机它考察的不仅是基础编码能力更是对时间/空间复杂度优化的深刻理解。问题的难点在于时间复杂度必须控制在O(n)空间复杂度理想情况下应为O(1)需要处理包含负数和重复值的特殊情况边界条件复杂如空数组、全负数数组等提示面试中遇到这个问题时面试官最期待看到的不是暴力解法而是能否想到原地哈希in-place hashing这种巧妙思路。2. 暴力解法与优化思路2.1 直观的暴力解法最直接的思路是从1开始逐个检查正整数对每个数字遍历整个数组第一个找不到的数字即为答案def firstMissingPositive(nums): i 1 while True: if i not in nums: return i i 1这个解法虽然简单但时间复杂度为O(n²)空间复杂度O(1)显然不符合题目要求。2.2 哈希表优化引入哈希表存储出现过的数字def firstMissingPositive(nums): num_set set(nums) i 1 while i in num_set: i 1 return i时间复杂度降至O(n)但空间复杂度也变成O(n)仍然不是最优解。2.3 原地哈希的突破真正的突破在于意识到长度为n的数组缺失的第一个正数必然在[1, n1]范围内。这个关键观察让我们可以在原数组上通过交换元素来实现哈希遍历数组将每个数字x交换到索引x-1的位置再次遍历第一个不满足nums[i] i1的位置就是答案3. 原地哈希的完整实现3.1 算法步骤详解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 13.2 关键操作解析核心的while循环完成了三件事检查当前数字是否在有效范围内1 ≤ x ≤ n检查目标位置是否已经存放了正确的值通过交换将当前数字放到它应该在的位置这个交换过程看似简单但实际时间复杂度分析很精妙虽然有两层循环但每个数字最多被交换一次所以总体仍是O(n)时间复杂度。4. 边界条件与特殊测试用例4.1 常见边界情况需要特别注意的测试用例包括空数组 → 应返回1全负数数组 → 应返回1包含重复值的数组已经包含1到n的完整数组 → 应返回n1单个元素数组如[1]或[2]4.2 调试技巧在实现过程中建议使用以下测试用例逐步验证test_cases [ ([1,2,0], 3), ([3,4,-1,1], 2), ([7,8,9,11,12], 1), ([], 1), ([1], 2), ([1,1], 2), ([2,2], 1) ]5. 算法优化与变种问题5.1 空间复杂度优化如果允许修改原数组原地哈希是最佳方案。如果不允许修改可以采用位图法用常数空间存储出现标记def firstMissingPositive(nums): # 使用符号位作为标记 n len(nums) # 处理非正数 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 15.2 相关变种问题缺失的第一个非负数允许0缺失的第二个正数在数据流中实时计算缺失的最小正数分布式环境下处理超大数组6. 实际应用场景这个问题虽然抽象但其核心思想在以下场景有实际应用数据库系统中的空闲ID分配内存管理中的页框分配分布式系统中的节点ID分配票务系统的座位分配算法7. 面试中的考察重点面试官通常会从以下几个维度评估候选人的表现能否快速理解问题并给出暴力解法能否发现暴力解法的问题并提出优化思路能否想到原地哈希这种非常规解法代码实现是否考虑各种边界条件能否正确分析算法复杂度8. 个人实现经验分享在实际编码中最容易出错的是交换逻辑的实现。我曾踩过两个坑交换顺序错误导致无限循环# 错误写法 nums[i], nums[nums[i] - 1] nums[nums[i] - 1], nums[i]应该先计算nums[i] - 1再交换。忽略重复元素处理 当数组中有重复元素时需要添加nums[nums[i] - 1] ! nums[i]的判断否则会陷入死循环。另一个实用技巧是在面试中可以先写出哈希表解法然后分析其空间复杂度再自然过渡到原地哈希的优化思路这样展示的思考过程更完整。