1. 题目解剖普通数组里藏着的送命题1.1 先看看题目到底让你干什么如果你在刷题列表里看到缺失的第一个正数这道题千万别被普通数组四个字骗了——它看着人畜无害实际是许多大厂面试和 LeetCode 41 的经典拦路虎。题目只有一句话给你一个未排序的整数数组找出其中没有出现的最小的正整数。限定条件却极其苛刻时间复杂度 O(n)空间复杂度 O(1)。先看几个例子感受一下输入[1,2,0]数组里有 1、2还有 0那么缺失的最小正整数是3输入[3,4,-1,1]数组里有 1、3、4还带着一个 -1那么缺失的最小正整数是2输入[7,8,9,11,12]数组里全是大于 6 的数一个正整数都没从 1 开始那答案就是1。注意这里有个容易理解错的地方题目说的是正整数所以 0 和负数都不算数。你不需要去管数组里到底有多少个元素、长得乱不乱你要找的是那个从 1 开始数第一个断档的正整数。1.2 暴力解法为什么活不过第一轮很多人第一反应是排序先sort然后从 1 开始往后找哪个数没出现就返回哪个。排序的时间复杂度是 O(n log n)空间复杂度是 O(1)比如原地快排。听着挺美但题目明确要求 O(n)直接枪毙。还有人想到哈希表把所有数丢进Set然后从 1 开始查查到没出现的就返回。时间复杂度确实是 O(n)但额外空间是 O(n)同样不满足要求。那能不能用位图、布尔数组能但仍然是 O(n) 额外空间。这道题真正的难点不在于你想不想得到用哈希表查缺失值而在于怎么把手上的数组本身变成哈希表做到既不额外开空间又能线性时间内完成查询。这才是普通数组这个前缀的真正含义没有特殊结构、没有额外辅助只有这个数组本身。1.3 普通数组的两个隐藏特征值域和索引天然错位仔细看这道题你会发现一个有意思的规律数组长度是 n那么缺失的最小正整数只可能落在 1 到 n1 这个区间里。为什么如果数组里恰好包含了 1 到 n 的所有正整数那答案必然是 n1但凡缺了其中任何一个那么第一个缺的整数就一定在 1 到 n 之间。换句话说答案根本不可能超过 n1。这个结论很朴素但它是整个解法的地基。因为答案范围被锁死在了[1, n1]我们就不再关心数组里那些没用的数字——负数、0、大于 n 的数它们在寻找缺失正数的过程中全是干扰项。同时数组本身有一个天然的数据结构索引。索引从 0 到 n-1一共 n 个槽位。如果把数字v放到索引v-1的位置上那么某个数是否出现就变成了某个索引位置上是否放着对应的数。这样一来我们把查找缺失的问题转化成了检查每个位置上的数是否和索引匹配的问题。这就是原地哈希的核心。2. 核心思路把数组变成一张自制的哈希表2.1 为什么答案一定在 [1, n1] 里再用一个生活化的例子解释一遍。假设你有 10 个盒子索引 0~9编号 1~10 的小球正整数每个盒子只能放一个对应编号的小球。如果小球不齐你从头检查盒子1 号盒没有 1 号球那缺失的就是 1如果 1~9 号盒都对了只有 10 号盒空着或者放错了那缺失的就是 10如果 10 个盒子全都对了说明 1~10 都在那缺失的就是 11。数组长度 n 就是盒子数。结论自然变成缺失的第一个正数不会小于 1也不会大于 n1。这个区间锁定是整个算法的前提也是一切巧妙操作的安全边界。有了这个前提我们就能把数组里0和n的元素视为无效值。比如长度 5 的数组里出现100这个 100 绝对不可能是我们要找的答案的候选者因为它超出了[1, 6]的范围。我们需要的是让数组里每个位置都尽量满足nums[i] i 1也就是让数字和索引一一对应。2.2 原地哈希数字和索引的归位游戏所谓原地哈希就是不额外开哈希表而是利用数组本身的索引来记录信息。这里的信息就是值为 v 的数是否出现过。具体操作思路是遍历数组如果遇到一个数v满足1 v n就把它放到索引v-1的位置上。比如v3就应该放到nums[2]。如果nums[2]已经被另一个数占了那就把那个数换出来继续循环处理。这个过程就像把散落在地上的球一个个捡起来放回对应编号的盒子里。这个思路为什么能工作因为当我们最终处理完整个数组后每个能归位的数字都已经到了它该在的位置。之后从头扫描第一个nums[i] ! i1的位置对应的i1就是缺失的最小正整数。如果所有位置都严格对应说明 1 到 n 全都在数组里答案就是n1。2.3 处理无效值先把垃圾清理掉归位之前先要把干扰项处理干净。常见做法是第一遍遍历把所有0或者n的元素统一改成一个哨兵值比如n1。为什么是n1因为n1本身不在合法答案的取值范围内答案最大才可能是 n1但它又是一个正整数不会在后续遍历中被误判成负数或者零造成逻辑混乱。而且用n1作为哨兵值不需要额外申请任何数据结构完美契合 O(1) 空间的要求。这一步看似多此一举其实很关键。试想如果不清理数组里既有负数又有大数归位时还要不断判断这个数在不在合法范围代码会变得又臭又长还容易漏判。先把垃圾统一成一个值后续逻辑就清爽多了。3. 三步实现从零手写原地置换解法3.1 完整代码Python 版为例以 Python 为例完整写法如下def firstMissingPositive(nums): n len(nums) # 第一步把所有无效值统一改为哨兵值 n1 for i in range(n): if nums[i] 0 or nums[i] n: nums[i] n 1 # 第二步循环置换把合法的值放到对应的索引位置 for i in range(n): while 1 nums[i] n and nums[i] ! nums[nums[i] - 1]: # 把 nums[i] 放到索引 nums[i]-1 的位置上 target_idx nums[i] - 1 nums[i], nums[target_idx] nums[target_idx], nums[i] # 第三步扫描找到第一个 nums[i] ! i1 的位置 for i in range(n): if nums[i] ! i 1: return i 1 # 全部归位说明 1~n 都存在答案是 n1 return n 1这段代码只有约 20 行但每一步都有讲究。下面拆开讲。3.2 第一步为什么必须先做预处理预处理循环里把0和n的数都改成n1。有人会问为什么不直接跳到第二步反正 while 循环里也会判断1 nums[i] n直接跳过去确实也能通过但后果是while 循环里会反复跳过那些无效值代码可读性下降更关键的是第二步的 while 循环需要多次交换如果数组里混着负数你在 while 循环条件里就必须额外处理负数场景容易漏掉边界。先统一清理掉等于把是不是合法值这个问题一次性解决后续只关心归位。这里还有一个细节预处理完之后数组里的元素只有两类——合法值1 到 n和哨兵值n1。哨兵值不会被 while 循环处理因为它不在1 nums[i] n范围内。这样第二步的 while 循环条件就可以写得非常简洁。3.3 第二步while 循环的陷阱与原理第二步是核心。外层 for 循环从头到尾遍历每个索引内层 while 循环负责把当前位置的数送到它该去的地方。关键点在于内层必须是 while不能是 if。为什么因为当你把nums[i]和nums[nums[i]-1]交换后换回来的那个数可能也是一个合法的、没归位的数。比如数组[3, 1, 4, 2]索引 0 上是 3交换后变成[4, 1, 3, 2]索引 0 上变成了 4而 4 也应该放到索引 3 上。如果用 if交换一次就跳出索引 0 上留下一个 4最后扫描时就会误判缺失。用 while就会一直交换下去直到当前位置要么放的是正确的数nums[i] i1要么是无效值哨兵值要么是重复值nums[i] nums[nums[i]-1]。每次交换的时间复杂度均摊是 O(1)。你可能担心看起来像 O(n^2)每个元素最多被交换几次一个元素一旦被放到它正确的位置就再也不会被换走。每个元素最多进行一次归位操作因此总交换次数不超过 n。整体时间复杂度严格 O(n)。这里特别注意nums[i] ! nums[nums[i] - 1]这个条件。它解决的是重复值问题。比如数组[2, 2]索引 0 上是 2目标索引是 1如果目标索引上的值也是 2那交换就没有意义而且会死循环。加上目标位置的值不等于当前值的判断遇到重复值就果断跳过既不交换也不处理避免无限循环。3.4 第三步扫描判定结果归位完成后数组应该呈现出一种尽量有序的状态每个位置 i 上要么放着i1要么放着哨兵值或重复值。这时候从头扫一遍找到第一个nums[i] ! i1的位置返回i1即可。如果扫描完整个数组都没找到不匹配的位置说明数组恰好是[1, 2, ..., n]的一个排列可能顺序不完全一样但归位后完全一致那缺失的最小正整数就是n1。这段逻辑其实就是在回答一个朴素问题从 1 开始数哪个数字在数组里缺席了只不过我们用索引位置作为签到表把寻找过程压缩到了 O(n)。3.5 其他语言的写法要点如果你用 C 或 Java核心逻辑完全一致但有几个语言层面的细节需要注意class Solution { public: int firstMissingPositive(vectorint nums) { int n nums.size(); for (int x : nums) { if (x 0 || x n) x n 1; } for (int i 0; i n; i) { while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1]) { swap(nums[i], nums[nums[i] - 1]); } } for (int i 0; i n; i) { if (nums[i] ! i 1) return i 1; } return n 1; } };C 和 Java 在第二步里有个隐蔽问题swap(nums[i], nums[nums[i]-1])这一行如果直接写nums[i] - 1在 swap 过程中会被求值一次然而很多语言在传参求值时右边的nums[i]可能在左边交换后被改变导致索引错乱。稳妥做法是先取target nums[i] - 1再交换。上面 Java 版本里我已经这样做了C 版本用swap时也要注意先存下目标索引int target nums[i] - 1; swap(nums[i], nums[target]);这个细节我在面试中见过不少人翻车。交换前索引算好交换后索引可能已经变了如果你直接依赖nums[i]去计算目标位置大概率会访问到错误下标甚至越界。3.6 复杂度分析为什么说它是线性且常数空间时间复杂度三次循环每次都是 O(n)。第二步的 while 虽然嵌套但每个元素最多被交换一次均摊 O(n)。总时间复杂度 O(n)。空间复杂度只用到了常数个临时变量没有额外数据结构O(1)。原地修改允许修改输入数组。如果面试官额外要求不能修改原数组那这个解法就不适用了需要另想办法比如用抽屉原理配合二分思想但那种做法通常不满足严格的 O(n) 时间。大多数情况下题目默认允许原地修改。4. 另一种经典思路负数标记法殊途同归4.1 用正负号当签到标记原地置换法是把数字放到它该在的位置属于物理归位。还有一种思路更抽象利用数组元素的符号位来记录某个数是否出现过。这也是原地哈希的变体而且代码在很多解法里比置换法更短。核心逻辑是我们不需要真的把数组排好序只需要在遍历时对每个合法值v把索引v-1位置上的数改成负数。最后扫描时哪个索引上的数还是正数说明那个索引对应的数字没出现过。4.2 完整实现步骤def firstMissingPositive(nums): n len(nums) # 第一步把所有非正数统一改成哨兵值 n1 for i in range(n): if nums[i] 0: nums[i] n 1 # 第二步对每个合法值 v把索引 v-1 位置的数标记为负数 for i in range(n): v abs(nums[i]) if 1 v n: # 如果该位置还是正数标记为负数 if nums[v - 1] 0: nums[v - 1] -nums[v - 1] # 第三步扫描第一个正数位置对应的数字就是缺失值 for i in range(n): if nums[i] 0: return i 1 return n 1注意几个关键点第一步把非正数改成n1这样所有元素在第二步取绝对值时不会产生负数干扰。n1是正数取绝对值还是它自己。第二步遍历时v abs(nums[i])很重要。因为数组在标记过程中会出现负数如果你直接取nums[i]而不取绝对值就会误把负数当作无效值跳过或者把v-1索引标记到错误位置。if nums[v-1] 0的判断是为了防止重复标记。如果两个相同的数出现两次第二次遍历时该位置已经是负数再把它取反就会变回正数导致判定错误。4.3 置换法和标记法对比怎么选维度原地置换法负数标记法核心操作交换元素位置修改元素符号需要 while 循环需要处理连续交换不需要单次遍历处理重复值通过nums[i] ! nums[nums[i]-1]判断通过if nums[v-1] 0判断取绝对值不需要必须代码直观度逻辑更直观但容易在交换细节上出错代码更短但符号逻辑需要想清楚适用场景面试讲解推荐思路好表达快速 AC、代码量优先时推荐我个人刷题时两种都写过。置换法的好处是可视化强你很容易跟面试官解释我现在在把数字放回原位标记法代码更短但面试时容易在为什么取绝对值和为什么判断正数上卡壳。建议两种都掌握面试时选自己更有把握的那个讲。5. 面试和实战中的高频坑老手也容易翻车的地方5.1 死循环是怎么来的原地置换法里最经典的翻车点就是 while 循环写成了 if。前面已经解释了交换一次后当前位置可能还是一个新的、未归位的数所以必须 while 直到当前位置稳定。还有一种死循环来自重复值。比如数组[1, 1]索引 0 上是 1目标索引 0 上也是 1如果 while 条件写的是nums[i] ! i1也就是1 ! 1为假不会进入那没问题但如果写的是nums[i] ! nums[nums[i]-1]少了某个条件可能在极端场景下交换两个相同的值永远跳不出去。最稳妥的 while 条件就是nums[i]是合法值1 到 n且nums[i] ! nums[nums[i]-1]。前者保证我们有资格处理后者保证不会自我交换。5.2 边界值n1、全是负数、全是大于 n 的数边界情况是算法题的照妖镜。我总结了几种必须心理有数的输入n 1数组[1]索引 0 上是 1归位后扫描发现nums[0] 1全部归位返回n1 2n 1数组[2]预处理阶段 2 大于 n1改成哨兵值 2扫描发现nums[0] ! 1返回 1数组[-1, -2, 0]全部改成哨兵值 n1 4扫描发现索引 0 是 4 不等于 1返回 1数组[100, 200]两个都大于 n2改成 3扫描返回 1。这些边界情况的共同规律是没有 1答案就是 1有 1 缺 2答案就是 2以此类推。掌握这个规律边界用例就不容易漏。5.3 原地修改的副作用如果要求不改变原数组怎么办这道题本身允许修改数组但面试官有可能加一个限制不能修改原数组。这时候原地哈希方案直接失效因为你必须改动数组才能记录信息。如果真遇到这种变种常见的应对思路是利用抽屉原理 二分答案在 [1, n1] 区间内我们可以二分答案。每次二分一个值 mid数一数组里有多少个元素落在 [1, mid] 区间内如果数量正好等于 mid说明 1~mid 全都在缺失值在右侧否则缺失值在左侧。时间复杂度 O(n log n)空间 O(1)。这种方案不修改原数组但牺牲了线性时间。如果题目同时要求 O(n) 时间和不修改原数组说实话很难同时满足通常题目不会这么变态。在实际工作中修改原数组的副作用往往更让人担心。比如你拿的是生产环境的数据绝不能为了算一个算法题结果把原数组改成面目全非。面试时如果遇到这题我建议先问清楚可以修改原数组吗很多候选人上来就写结果面试官一问才发现题目要求不能改白费功夫。5.4 常见问题速查表问题原因解决方案while 循环死循环交换后当前索引还有未归位数但用 if 只处理一次内层改用 while直到当前位置稳定重复值导致死循环目标位置和当前值相同还强行交换while 条件加nums[i] ! nums[nums[i]-1]标记法结果错误取nums[i]时没取绝对值把负数当成无效值用v abs(nums[i])标记法重复标记同一值出现两次第二次取反把负数变回正数先判断if nums[v-1] 0再标记负数未处理预处理遗漏导致 while 条件判断越来越复杂第一遍统一将非正数改成哨兵值 n1答案返回 n1 时机搞错扫描完所有位置没发现不匹配应该返回 n1循环结束后单独返回 n1交换时索引越界nums[i]-1不是合法索引确保第一步把所有不在 [1, n] 的元素改成哨兵值5.5 一个鲜为人知的优化跳过已经在正确位置的值在置换法的第二步中for 循环遍历索引 i 时如果nums[i] i1说明当前位置已经归位直接 continue。这个判断其实已经在 while 条件里隐含了因为nums[i] i1时nums[i] nums[nums[i]-1]恒成立因为nums[i]-1 i所以 while 条件整体为假不会进入循环。但是显式写出来可以提升可读性for i in range(n): if nums[i] i 1: continue while 1 nums[i] n and nums[i] ! nums[nums[i] - 1]: target nums[i] - 1 nums[i], nums[target] nums[target], nums[i]这样代码的意图更明显已经对的别碰不对的往对的方向交换。面试时这样写面试官一眼就能看懂你在干嘛。6. 题感迁移怎么一眼识别原地哈希题型6.1 这类题目的共性模式刷题到一定量你会发现很多题目表面上长得完全不一样内核却惊人一致。凡是满足以下特征基本都可以尝试原地哈希输入是一个整数数组要求找缺失的数字、重复的数字、出现次数异常的数字答案范围往往和数组长度有关通常能锁定在一个小区间内严格要求 O(1) 额外空间。典型代表有LeetCode 448 找到所有数组中消失的数字给你一个长度为 n 的数组数字范围在 [1, n]找出 [1, n] 中没出现的数字。用负数标记法简直顺手拈来。LeetCode 287 寻找重复数数组长度为 n1数字范围 [1, n]要找那个重复的数。虽然更经典的解法是快慢指针看成链表找环但你也可以尝试用原地标记的思路。LeetCode 268 丢失的数字数组包含 [0, n] 中 n 个数找出缺失的那个。可以用异或也可以用索引归位。剑指 Offer 03 数组中重复的数字数组长度 n数字范围 [0, n-1]查找重复值。这题用原地哈希也能解。掌握了缺失的第一个正数就等于掌握了一套处理值域和索引范围重叠问题的通用方法论。遇到类似题目不要急着排序或开哈希表先想想能不能用数组本身做文章。6.2 拿到题目后的三问自检法我平时刷题有个习惯拿到一道数组题先问自己三个问题第一**答案的取值范围是什么**如果是找缺失的正整数那答案必然在 [1, n1]如果是找重复数那重复值必然在 [1, n]如果是找消失的数那范围也必然是 [1, n]。取值范围一旦确定原地哈希的基本盘就稳了。第二**数字和索引之间有没有天然映射**正整数的值 v 对应索引 v-1这个映射是所有这类题的通解。如果题目给的是其他映射关系比如值域是 0 到 n-1那就是v对应索引v。总之你要找到一个规则让值是否出现变成索引位置上是否有标记。第三**题目允许修改数组吗**允许就用原地哈希不允许就只能用二分、快慢指针或异或等不修改数组的方案。这个问清楚能帮你避开很多弯路。这三个问题想清楚写代码只是时间问题。很多同学一上来就写写到一半发现条件不符合又推翻重来反而浪费时间。6.3 纸上模拟一行代码不写也能理清逻辑这里分享一个我调试这题时用的土办法拿一个具体数组比如[3, 4, -1, 1]在纸上画出四个格子每个格子顶上标上索引号 0、1、2、3下面写上当前值。然后一步一步执行预处理和交换预处理[3, 4, 5, 1]哨兵值 n15i0nums[0]3目标索引 2交换后[5, 4, 3, 1]继续 whilenums[0]5 不合法跳出i1nums[1]4目标索引 3交换后[5, 1, 3, 4]继续 whilenums[1]1目标索引 0交换后[1, 5, 3, 4]继续 whilenums[1]5 不合法跳出i2nums[2]3目标索引 2但nums[2] nums[nums[2]-1]因为 3 已经在索引 2 上跳过i3nums[3]4同理已在正确位置扫描nums[0]1正确nums[1]5 ! 2返回 2在纸上走完一遍你对代码里那些 while 条件的理解会深得多。尤其是为什么交换后还要继续 while纸上模拟一次立刻明白。6.4 一个建议把这道题当母题反复练我个人做这道题有个心得它太适合当母题了——一个算法思想原地哈希贯穿了好几个高频面试题。你花一个晚上把这道题彻底吃透等价于同时预习了消失的数字重复数字这几类变种。建议你在本地环境里把置换法和标记法各写三遍直到不查资料也能流畅写出来再试着不看题解把 448 和 287 也做一遍。遇到面试官追问还有没有其他解法你把置换法和标记法都讲一遍自然显得思路开阔能把复杂度分析讲明白尤其是为什么 while 整体仍然 O(n)基本就能让面试官点头了。最后说一个我踩过很多次坑之后的习惯凡是要求 O(1) 空间处理整数数组的题目我不会第一时间去排序或开集合而是先盯着 数组长度 和 元素值域 看三秒钟。值域和长度一旦产生了交集原地哈希的机会就在眼前。这道缺失的第一个正数把这种题型玩到了极致把它吃透你等于解锁了一整类面试题的通关钥匙。