最近在准备跳槽刷力扣hot100的时候遇到第41题“缺失的第一个正数”没想到后来在某大厂的一面里直接被问到了原题。说实话看到题目那一刻我心里有点复杂——见过是见过但这题属于典型的“看着简单真写起来容易翻车”的类型。面试官把题目写到白板上的时候特意强调了两个约束时间复杂度O(n)空间复杂度O(1)。这句话基本定调了排序不行开哈希表也不行你得想别的招。这篇文章我想把这题从头到尾讲透。从暴力解为什么不行到原地哈希的本质到两种可以AC的写法再到我实际调试时踩过的坑以及面试官大概率会追问的变体题。无论你是刚开始刷题的新手还是准备冲刺大厂的老兵这篇应该都能帮你少走点弯路。1. 题目到底在问什么先读懂再动手1.1 原题考点与限制条件原题描述很简单给你一个未排序的整数数组 nums请你找出其中没有出现的最小正整数。示例很典型nums [1,2,0]返回3nums [3,4,-1,1]返回2。表面上看就是“从1开始找第一个不在数组里的正整数”但真正决定题目难度的不是问题本身而是那两条硬性约束时间复杂度O(n)空间复杂度O(1)。我刚开始刷题的时候觉得这题没什么难度排序后从1开始扫遇到不连续就返回搞定了。但排序是O(nlogn)直接违背时间约束。用哈希集合把正整数都装进去再从1开始找O(n)时间很轻松但额外空间是O(n)又违背空间约束。这两条路全被堵死之后题目才真正开始变得有意思——面试官想看的就是你能不能另辟蹊径在“原地”二字上做文章。这题在力扣hot100里的定位是“中等难度”但它背后的思维量其实超过不少困难题。它考察的核心能力是能否把数组本身当作一个可用的数据结构而不是条件反射地申请额外空间。这个能力在真实工程里太重要了因为很多场景下内存就是稀缺资源能原地解决就绝不额外开销。1.2 面试官在观察哪几件事一面算法题面试官其实不完全看你的提交是否正确他更想看你的思维过程。我后来复盘那次面试发现他其实在观察四件事。第一你能不能先分析暴力解的不足再一步一步演进到最优解。很多人上来就闷头写最优解其实未必是加分项——因为面试官不知道你是背的题还是真的理解。反而是那种“先给两个不太行但思路自然的解法再自己否定掉最后引出真正的答案”的展示方式最能体现解决问题的能力。第二边界情况有没有想全。空数组返回1全负数返回11到n全部出现返回n1重复数字怎么处理。这些细节一漏代码跑起来就会出问题面试官只要随手丢一个用例就能测出来。第三代码风格和沟通节奏。一边写一边解释每三两行就说一句“这一步是干什么的”会让面试官觉得你思路很清晰。最怕的是闷头写半天最后丢出一坨代码让人家自己看。第四改bug时的反应。面试官有时会故意打断你“你这个代码在[1,1]上会死循环吧”这时候能不能快速定位问题、解释原因、修正代码比一开始就写出完美代码更能反映真实水平。2. 思路演进从暴力到原地哈希的四层思考2.1 所有新手都会想到的两个解法为什么不够先说第一个直觉排序。把数组排好序然后从1开始往后找。排序后数组变成有序的如果当前数字等于期望值expect就expect加1继续往后看如果当前数字大于expect说明expect缺失直接返回。空间没问题O(1)但排序本身就O(nlogn)了在题目要求的O(n)面前直接被淘汰。再说第二个直觉哈希集合。把所有正整数丢进一个HashSet然后从1开始while True循环第一个不在集合里的数就是答案。这个方案时间O(n)非常快但空间O(n)。很多面试者卡在这一步觉得“时间已经最优了空间稍微超一点好像也没什么大不了”但实际上题目明确写了O(1)空间这就是红线踩了就扣分。但注意这两个“错误”答案在面试中是有价值的。我刚拿到题的时候反而故意先跟面试官说“排序需要O(nlogn)哈希表需要O(n)空间都不符合要求那么问题来了有没有办法把哈希表藏到数组内部”这一说面试官眼神就亮了——因为他看到你自带复杂度分析意识而不是背答案。2.2 关键洞察答案一定在[1, n1]这个区间里所有解法的地基都在于一个数学观察假设数组长度是n那么最终答案一定落在1到n1之间。道理非常简单数组只有n个位置最多只能容纳n个不同的正整数。如果1到n全部出现了那最小的缺失正数只能是n1只要有一个没出现答案就是那个最小的断档数字它必然在1到n之间。我习惯用一个生活类比来理解想象你有n个抽屉想检查“从1号开始连续的数”缺到几号。如果n个抽屉里正好装了1到n每个数一次那下一个要检查的就是n1号。如果有某个抽屉里的号数跟抽屉编号对不上或者压根就没出现那断档的地方就是答案。整个问题就变成了“把每个数放进对应的抽屉”。基于这个观察我们可以立刻排除一批干扰元素负数、0、大于n的数都不可能是答案所以处理的时候完全不用管它们。这就把问题空间从“所有整数”压缩到了“1到n”相当于把一个大问题缩小成了一个小范围内的排序/查找问题。2.3 把数组当成哈希表原地哈希的核心思想常规哈希表能解决问题是因为它能O(1)判断“某个数x是否出现过”。既然额外空间不能用那就让数组自己来扮演这个哈希表。具体做法数组下标i天然对应数字i1。如果我能把每个出现在[1,n]范围内的数字x放到下标x-1的位置那么扫描数组时第一个nums[i] ! i1的位置就说明i1这个数字缺失了。这个过程就像玩“麻将归位”。每一张牌都有属于自己的坑数字3必须去“坑3”也就是下标2的位置数字5必须去下标4的位置。把每一张牌放到它该待的坑里最后哪个坑里的牌不对哪个数字就缺失了。如果所有坑都对了说明1到n全齐了答案就是n1。核心问题就变成怎么在O(n)时间内完成归位而且不能用额外空间答案就是“交换”。从头开始遍历如果当前位置的数字在[1,n]范围内而且它没在自己的正确位置就把这个数字和正确位置上的数字交换。换过来的数字继续判断直到当前位置的数字不在[1,n]或已经归位才往前走。这样一来每个数字最多被交换一次整体时间O(n)空间O(1)完美满足约束。3. 核心实现两种主流写法的完整拆解3.1 写法一交换归位法面试首选先给出我最推荐的写法Python实现非常简洁def firstMissingPositive(nums): n len(nums) i 0 while i n: num nums[i] # 只有1到n范围内的数字才有“归位”的意义 if 1 num n and nums[num - 1] ! num: # 把num放到它该待的位置下标 num-1 nums[num - 1], nums[i] nums[i], nums[num - 1] else: i 1 # 归位完成后第一个值不等于下标1的位置就是缺失的正数 for i in range(n): if nums[i] ! i 1: return i 1 # 如果1到n全出现了答案是n1 return n 1有几个细节必须说清楚。第一为什么用while而不是for因为交换过来的数字可能同样需要归位。比如当前位置换过来一个55可能需要再去下标4的位置如果你用for循环i直接递增这个刚换过来的5就漏掉处理了。while循环每一次迭代都重新检查当前位置直到当前位置的数字要么不在[1,n]要么已经归位。第二交换条件里为什么要写nums[num - 1] ! num这是防止死循环的关键。如果目标位置已经有相同的值说明这个数字已经就位交换只会原地打转。具体例子后面讲坑的时候会细说。第三不在[1,n]范围内的数字直接i跳过。它们不可能是答案留在原地就行不用专门挪走。这一点很多新手不理解总觉得“负数留着会不会影响后续判断”实际上完全不会因为扫描阶段只检查nums[i] ! i1负数不等于i1只会让这个位置被判定为“缺失”动作越少越不容易出错。我拿面试时手写的那个用例[3,4,-1,1]来模拟一遍完整流程初始数组[3, 4, -1, 1]n4i0。i0num3在[1,4]内目标下标是2nums[2]-1不等于3交换。数组变成[-1, 4, 3, 1]i保持0。i0num-1不在[1,4]内ii1。i1num4目标下标是3nums[3]1不等于4交换。数组变成[-1, 1, 3, 4]i保持1。i1num1目标下标是0nums[0]-1不等于1交换。数组变成[1, -1, 3, 4]i保持1。i1num-1不在[1,4]内ii2。i2num3目标下标是2nums[2]3等于3说明已经归位ii3。i3num4目标下标是3nums[3]4等于4已经归位ii4循环结束。扫描阶段i0时nums[0]1正确i1时nums[1]-1不等于2返回2。答案就是2完全正确。3.2 写法二负号标记法思路最直观交换归位法面试中最常用但还有另一种写法也很经典负号标记法。它的思路完全不同但同样O(n)时间O(1)空间。核心思想是用数组元素的正负号来记录“某个数字是否出现过”。如果数字x出现过就把下标x-1位置的元素标记成负数最后扫描时第一个正数所在的位置就是答案。def firstMissingPositive(nums): n len(nums) # 第一轮把所有非正数替换成 n1避免影响后续标记 for i in range(n): if nums[i] 0: nums[i] n 1 # 第二轮遍历数组出现过的数字x把下标x-1标记为负数 for i in range(n): x abs(nums[i]) if 1 x n: nums[x - 1] -abs(nums[x - 1]) # 第三轮第一个正数的下标i说明i1没出现过 for i in range(n): if nums[i] 0: return i 1 # 全部是负数说明1到n都存在返回n1 return n 1这个写法的核心是第二轮循环里为什么要用abs(nums[i])。因为数组在遍历过程中某些位置已经被标记成负数了直接取nums[i]会拿到负值取绝对值才能还原出原始的“这个位置本来记录的数字”。另外标记时用-abs(...)而不是直接取负号是为了防止同一个数字出现多次时“负负得正”导致标记被抵消。我第一次写的时候就直接nums[x - 1] -nums[x - 1]遇到重复数字就出bug后来才改成-abs。负号标记法的优势是三个for循环结构非常清晰不需要处理while交换逻辑上更贴近“哈希表”的直觉。缺点是必须把非正数先替换掉否则0和负数在取绝对值后会造成误标记。而且整个数组全变成负数后要判断的是“正数位置”语义上需要绕一下。面试中我更推荐先讲交换归位法因为它直接体现了“让数组本身有序化”的思路。但如果面试官追问“还有没有别的做法”负号标记法就是很好的补充答案能展示你对这个问题的理解不止一种。3.3 复杂度与正确性的硬核分析先说时间复杂度的细节。交换归位法看起来是while循环套交换总感觉像O(n^2)。但实际上每次交换都会把一个数字放到它最终的正确位置上而且一旦就位就不会再被换走。每个元素最多参与一次“被换到正确位置”的操作所以总交换次数不会超过n次。while循环每次迭代要么做一次交换要么i前进一步无论如何总操作数都是O(n)。这个证明我很喜欢因为它特别反直觉——表面像嵌套循环实际上是线性复杂度。空间上更好说整个过程只用了一个临时变量存num常数级额外空间。扫描阶段只用了一个i所以空间O(1)。再谈正确性。交换归位法的循环不变量是当i跳过某个位置时该位置要么已经满足nums[i]i1要么nums[i]不在[1,n]范围内。也就是说我已经决定这个位置“不需要再动了”。归位结束后从0到n-1扫描第一个不满足nums[i]i1的位置对应的数字i1必然没在数组中出现过。这是由“归位”的语义直接保证的——如果i1出现过它一定被换到了下标i的位置。负号标记法的正确性同样直接。第二轮结束后nums[i]为负数当且仅当数字i1在原始数组中出现过。那么第一个正数位置i就表示i1从未出现是缺失的最小正整数。唯一要注意的是第一轮把所有非正数改成n1不会影响后续扫描因为n1本身不在[1,n]范围内不会触达任何下标。4. 踩坑实录与调试技巧这题最容易在哪儿翻车4.1 负数和零处理不当导致的连锁问题交换法里负数其实天然是安全的。因为判断条件1 num n会把负数挡在交换之外直接i跳过。但很多新手会觉得“负数留在数组里不舒服”非要先把负数挪到数组末尾或者清零结果引入了一堆不必要的复杂逻辑。相信我原数组里有多少负数都不影响最终答案它们不参与任何判断只是“占了个坑”。负号标记法里负数处理就讲究多了。第一轮必须把所有非正数统一替换成n1这一步不能省。如果数组里有0第二轮abs(0)是0不在[1,n]范围内不会误标记但0本身在第三轮扫描时是正数会被误判为“i1缺失”造成错误结果。至于负数如果不替换取绝对值后可能变成1到n之间的正数直接触发错误标记。所以“先把非正数全部变成n1”是负号标记法的前置条件漏了必然翻车。4.2 重复元素引起的死循环这个坑我印象太深了。我第一次撸交换法时把交换条件写成了nums[i] ! i 1结果在[1,1]这种用例上直接死循环。原因在于i0时num1此时目标下标应该是num-10但我的错误条件判断的是“当前位置的值是否等于位置编号1”这也可以理解为“这个数该不该留在这里”。在[1,1]里位置0的1确实是该留在位置0的所以条件为假应该i。但我的错误写法里nums[0] ! 1为假所以没交换然后i其实侥幸没死循环。真正危险的是[2,2]这种i0时num2错误条件nums[0] ! 1为真于是尝试交换位置0和位置1的数字。交换后数组还是[2,2]然后i不前进又重复这个过程无限循环。正确的交换条件必须写成nums[num - 1] ! num比较的是“当前数字num”和“目标位置已有的数字”是否相同。如果目标位置已经有同样的值说明数组里已经有一个num归位了当前这个num是多余的不需要再交换直接i跳过去。这一点在面试现场很重要面试官只要随手写个[2,2]你没提前想到就会当场卡住。4.3 一个被我反复验证的测试用例清单刷这种老题一定要有一套自己的测试用例清单每次写完代码直接跑一遍比在纸上空想要靠谱得多。我这题固定用下面这几个用例输入期望输出覆盖要点[]1空数组最基础边界[1]21已经出现答案在n1[0]1零不干扰答案[-5]1负数不干扰答案[1,2,0]3官方用例有零有缺失[3,4,-1,1]2乱序负数缺失经典组合[1,2,3]41到n全部出现返回n1[7,8,9,11,12]1全是超大正数答案最小[1,1]2重复数字防死循环核心用例[2,2]1重复缺失1另一个防死循环用例每次写完代码我习惯按这个清单跑一遍。不用全跑至少挑[3,4,-1,1]、[2,2]、[1,2,3]三个基本能覆盖所有边界和核心逻辑。面试时如果时间紧张手动跑一个普通用例再跑一个边界用例已经足够证明代码的可靠性了。4.4 现场写代码时容易忽略的细节第一个细节是交换时的索引问题。Python的多重赋值nums[a], nums[b] nums[b], nums[a]很安全但如果面试官要求你用C或Java必须先用临时变量存下一个值或者用swap函数。如果是手动三步交换先存int target nums[i] - 1再操作nums[target]和nums[i]顺序别反了。我见过有人先改nums[i]再去算target结果target值已经变了索引直接越界。第二个细节是扫描阶段的下标判断。第三轮扫描应该判断nums[i] ! i 1不是nums[i] ! i。这个错误虽然低级但在紧张状态下真的容易犯。我自已在模拟面试时就错过一回当时面试官笑着指了指白板我才意识到下标偏移了一位。第三个细节是返回值。如果数组里1到n全部出现了扫描阶段找不到任何“错位”位置要返回n1。很多新手只写了扫描里的return忘了最后这个return n 1结果在[1,2,3]这种用例上报错。第四个细节是while循环和i递增的关系。有些人把交换逻辑写在if里交换后忘了continue或主动调整i导致循环逻辑混乱。我建议的写法就是满足交换条件就交换但不递增i不满足条件就i。这个模式一旦固定下来就不容易出错。5. 面试官可能追问的扩展题与应变思路5.1 追问一数组不允许修改怎么办这个问题我被问到过也是这题最常见的追问。既然不能原地修改数组那交换法和负号标记法都不能用了。最简单的替代方案是开一个长度为n的布尔数组遍历原数组时把nums[i]对应下标的布尔值置为true然后从1开始找第一个false的位置。时间O(n)空间O(n)但这个空间开销在“不允许修改数组”的前提下是被允许的。面试官如果继续逼问“空间能不能再省”那就上二分法。答案在1到n之间二分查找答案区间每次取mid统计原数组里“值在1到mid之间”的正整数个数。如果个数等于mid说明1到mid全部出现了缺失值在右半边如果个数小于mid说明左边有缺失把区间往左缩。时间O(nlogn)空间O(1)。面试时不用写完代码能说清楚思路就已经过关了。5.2 追问二数据量超出内存怎么办这种场景在工程里更真实数组太大没法一次性加载到内存。那原地哈希里的“原数组”都不存在只能分批处理。常见思路是分块扫描先把数据分成若干块每块加载到内存后用同样的哈唏思想统计或者用位图记录每个数字是否出现过位图大小取决于值域范围。这类问题面试一般只聊思路聊到“用外排序或分块缩小范围”基本就结束了面试官主要想看你有没有大数据的意识。5.3 把这道题的经验迁移到其他高频题原地哈希这个思想不止一次救过我。比如“找出数组中消失的数字”那道题给你一个长度为n的数组元素值在1到n之间有的数字出现两次、有的出现一次让你找哪些数字没出现。解法就是类似负号标记法遍历数组把nums[abs(nums[i])-1]标记为负数最后为正数的位置就是消失的数字。再比如“找出数组中所有重复的数字”同样的套路。这些题共享同一个核心洞察值域和下标范围一致就可以用数组本身记录状态。我刷题时间长了养成一个习惯看到“必须O(1)空间”这种约束第一反应就是“能不能用原数组做标记或者当哈希表”。这个思维模式从第41题开始建立后来在好几道hard题上都派上了用场。面试的时候如果遇到没刷过的题我也会先沿着这个方向思考往往能找到突破口。5.4 面试表达上的细节最后聊聊面试现场怎么把这题讲得漂亮。我那次一面之所以能顺利过关回头想有四个表达细节值得参考。第一先花30秒跟面试官确认题意和约束。我会说“我确认一下未排序整数数组找最小的缺失正整数要求O(n)时间和O(1)额外空间对吗”这个确认动作不只是形式它还能让面试官知道你抓重点的能力。第二把两个直觉错误解法说出来并自否定。这能展示你的分析思维而不是背题。原话大概是“排序的话O(nlogn)不合格哈希表空间O(n)不合格所以问题变成了怎么在数组内部完成哈希表的职责。”第三点出核心洞察后再写代码。就说“答案一定在1到n1之间所以我可以把每个在范围内的数字放到它对应的下标位置”这句话一出口面试官基本就对你放心了。第四写完代码主动跑一个用例。手动执行[3,4,-1,1]的模拟过程让面试官看到你的代码不是“看起来对”而是真的能跑。这四步做完即使代码有小瑕疵面试官也会认为你思路清晰、沟通顺畅愿意引导你去修正。反之如果闷头写完也不解释哪怕AC了也容易被判定为“缺乏沟通能力”。我个人把第41题前前后后写了不下十遍每次重写都有新收获。最初只是背了个模板后来才真正理解“用数组当哈希表”的妙处以及为什么交换法的while循环天生就比for循环更适合这个场景。面试那天当我讲完“答案一定在[1,n1]”这个点时看到面试官微微点头我心里就踏实了一半。最后分享一个自己的小习惯凡是遇到“缺失”“重复”这类问题我都会先问自己三个问题——值域是什么位置能不能复用能不能用数组本身记录状态这三个问题想清楚大部分类似题目的解法都会自己冒出来。希望这篇能帮你在下一次面试中少踩几个我踩过的坑。