算法通关手册：LeetCode 0041「缺失的第一个正数」——原地哈希实现 O(n) 时间与 O(1) 空间的完整剖析

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南围绕 AlgoNote「算法通关手册」中 LeetCode 0041 缺失的第一个正数题解 展开深入讲解「原地哈希In-place Hashing」这一在数组类难题中极为重要的技巧。通过阅读本文你将掌握如何在不申请额外哈希表的前提下把数组本身当作哈希表使用从而同时满足时间复杂度O(n)与常数级空间复杂度的苛刻要求并能迁移到其他查找缺失/重复元素类问题中。题目概览题目编号0041中文题名缺失的第一个正数First Missing Positive标签数组、哈希表难度困难该题被收录在 0001-0099 题解目录、算法分类题单归类于「数组、哈希表」以及 面试 100 题清单 中是算法面试中考察「空间复杂度优化」的代表性题目。题目描述与约束描述给定一个未排序的整数数组nums。要求找出其中没有出现的最小的正整数。说明与数据范围1 ≤ nums.length ≤ 5 * 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1要求实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案注意数据范围中的两个关键信息数组长度最大可达50 万元素取值横跨整个 32 位整数范围既有负数也有远超数组长度的大正数。这意味着任何基于排序O(n log n)或基于普通哈希集合O(n)空间的直接解法都不满足题目要求。示例示例 1输入nums [1,2,0] 输出31、2均已出现缺失的最小正整数为3。示例 2输入nums [3,4,-1,1] 输出21已出现2缺失因此答案为2。解题思路思路 1哈希表、原地哈希朴素思路及其局限如果使用普通的哈希表我们只需要遍历一遍数组将对应整数存入哈希表中再从1开始依次判断对应正数是否在哈希表中即可。但此时空间复杂度为O(n)不满足题目常数级别额外空间的要求。关键观察一个长度为n的数组能够承接的正整数范围是[1, n]。因此缺失的第一个正数要么落在[1, n]区间内要么当1 ~ n全部出现时就是n 1。换言之答案只可能来自[1, n 1]这个集合数组下标天然可以作为这些候选值的哈希地址。原地哈希的做法把当前数组本身视为一张哈希表让值为x的元素回到下标为x - 1的位置遍历一遍数组将当前元素放到其对应位置上。例如元素值为1的元素放到数组第0个位置元素值为2的元素放到数组第1个位置以此类推仅对值落在[1, n]范围内的元素执行归位其余元素可忽略。再次遍历数组。遇到第一个元素值不等于下标 1的位置该位置对应的正整数i 1就是缺失的第一个正数。如果遍历完都没有找到说明1 ~ n全部出现缺失的第一个正数是n 1。返回结果。这一思想的根基正是 哈希表专题 中介绍的「直接定址法」Hash(key) key此处再减去偏移量1映射到数组下标。由于答案的取值空间被严格限制在[1, n 1]直接定址不会产生冲突也就不需要任何冲突处理天然契合哈希函数计算简单、无冲突的理想要求。思路 1代码以下代码完整继承自 first-missing-positive.md并补充了关键注释class Solution: def firstMissingPositive(self, nums: List[int]) - int: size len(nums) # 第一遍遍历原地哈希把每个值 x1 x size放到下标 x - 1 处 for i in range(size): # 只有当值合法在 [1, size] 内且尚未归位时才进行交换 # nums[i] ! nums[nums[i] - 1] 这个条件同时防止了重复值导致的死循环 while 1 nums[i] size and nums[i] ! nums[nums[i] - 1]: index1 i index2 nums[i] - 1 nums[index1], nums[index2] nums[index2], nums[index1] # 第二遍遍历第一个位置错位处即缺失的第一个正数 for i in range(size): if nums[i] ! i 1: return i 1 # 1 ~ size 全部就位缺失的是 size 1 return size 1思路 1复杂度分析时间复杂度O(n)其中n为数组nums的元素个数。虽然第一遍遍历中存在while循环但每个元素至多被交换到正确位置一次交换次数整体不超过n因此均摊仍是线性复杂度。空间复杂度O(1)所有操作均在原数组上进行只使用常数级别的额外变量。代码细节与边界情况解析理解下面几个细节才能真正把这段代码吃透为什么交换而不是直接赋值直接nums[nums[i] - 1] nums[i]会覆盖掉目标位置上的原有值导致信息丢失。必须采用交换才能让被挤走的元素继续参与后续归位。while循环的终止条件nums[i] ! nums[nums[i] - 1]这一条件非常关键。当目标位置已经存放着相同值时即重复元素继续交换会造成两个相同值反复互换、陷入死循环。该条件在归位完成或遇到重复值时终止循环。值域过滤1 nums[i] size负数、0以及大于size的正数都不可能成为答案答案最大为size 1因此无需归位直接跳过。这也保证了交换操作永远不会越界访问。交换顺序的正确性代码先分别取出index1、index2再交换避免了在单行交换中因右侧求值顺序问题导致的错误是严谨的写法。边界用例演示nums [1]第一遍归位后仍为[1]第二遍nums[0] 1循环结束返回size 1 2。正确。nums [7, 8, 9, 11, 12]所有元素均超出[1, 5]不参与归位第二遍nums[0] ! 1立即返回1。正确。nums [1, 2, 0]0被过滤1、2归位后数组为[1, 2, 0]第二遍nums[2] ! 3返回3。与示例 1 一致。同源题型的横向延伸「原地哈希」并非本题独有它是在已知值域、查找缺失或重复类问题中的通用利器与本题共享同一套思维模型0268. 丢失的数字值域为[0, n]缺失数字同样可以借助数组下标定位该题题解还给出了数学求和这一O(1)空间的替代方案可作为对比阅读。0287. 寻找重复数值域为[1, n]查找重复元素题解提供了二分计数与可进一步推导的原地哈希/链表判环等不同路径。它们的共同特征是元素值域与数组长度强相关从而允许把值编码进下标。理解了 0041 的原地哈希后再回看上述题目会轻松很多。仓库中的延伸阅读数组基础与随机访问见 01_01_array_basic.md其中介绍了数组连续内存 下标寻址的特性这正是原地哈希能够成立的前提——下标本身就是 O(1) 的地址。哈希表基础见 03_06_hash_table.md其中「直接定址法」「哈希函数设计」两节与本题的映射思路直接对应。本题在仓库中的归类与收录见 0001-0099 题解目录、算法分类题单、面试 100 题清单 与 题解总目录。小结「缺失的第一个正数」是极少数同时卡住时间O(n)与空间O(1)两道硬性约束的数组难题其破局点在于三个层层递进的观察答案必然落在[1, n 1]数组下标可以充当哈希地址交换而非覆盖可以保证信息不丢失。掌握原地哈希后你不仅能独立 AC 本题还能将其推广到寻找重复数、丢失数字等一系列值与下标互相对应的经典问题中这是算法面试中值得反复打磨的一类核心技巧。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐N_m3u8DL-RE 流媒体下载完整指南M3U8/DASH/HLS 快速上手教程N_m3u8DL RE 流媒体下载完整指南M3U8/DASH/HLS 快速上手教程 N_m3u8DL RE 是一款跨平台的命令行流媒体下载工具支持 DASHCLI音视频LeetCode 41 缺失的第一个正数First Missing Positive五种解法与 O(1) 空间哈希技巧全解析LeetCode 41 缺失的第一个正数First Missing Positive五种解法与 O 1 空间哈希技巧全解析 本文基于 GitHub 推荐项示例工程教程LeetCode 136 只出现一次的数字用异或运算实现 O(n) 时间 O(1) 空间解法LeetCode 136 只出现一次的数字用异或运算实现 O n 时间 O 1 空间解法 导读 LeetCode 136「只出现一次的数字」Single N文档教程知识库上一篇终极跨平台Unity破解指南UniHacker完整使用教程下一篇如何用Layout Card彻底改造你的Home Assistant界面完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考