前阵子面某大厂的一面面试官没寒暄几句就在共享屏幕上甩了一道算法题——某刷题平台Hot 100榜单里的第41题缺失的第一个正数。看到题目内容我心里稳了一半这题我做过不止一遍但等动手写的时候才发现越是经典原题越容易在细节上翻车。面试官明确要求时间复杂度O(n)额外空间O(1)也就是说排序和哈希表都是妥妥的扣分项。这篇文章我完整复盘一下当时的思路、手撕代码以及面试官追问到让我冒冷汗的几个点希望能帮到同样在备战的你。如果看到这道题你的第一反应是“排序然后扫一遍”那说明你和大部分人的反射弧一样但这不是面试官想要的。因为排序就是O(n log n)根本达不到O(n)的要求。也有人会说“那就开一个布尔数组从1开始找第一个false”空间O(n)同样不行。到这里普通解法已经被封死了。真正的故事要从“答案最大只能是n1”这个洞察开始讲。1. 题目到底在问什么看穿“最小正数”的陷阱1.1 题目还原与直觉第一反应题目本身很短给你一个未排序的整数数组 nums请你找出其中没有出现的最小的正整数。示例1输入 [1,2,0]输出3。示例2输入 [3,4,-1,1]输出2。示例3输入 [7,8,9,11,12]输出1。注意这里问的是“最小正整数”不是“缺的数字”。数组里可以有负数、零、重复数字、甚至超过数组长度的数字。例如 [7,8,9,11,12]里面没有1那答案就是1很直接。但 [3,4,-1,1] 这种正数有3、4、1缺2所以答案是2。如果数组是 [1,2,3,4]1到4都在那答案就是5也就是 n1。看到题目后的直觉先找最小的正数最简单粗暴的办法是排序。排完序后从头扫描定义一个变量 expect 1遇到正数就和 expect 比较相等就 expect不等就返回 expect。代码量大概十行逻辑也没有漏洞。比如 [3,4,-1,1]排序后是 [-1,1,3,4]扫描-1忽略1等于expect1expect变23不等于2返回2。没问题。但是问题来了排序的时间复杂度是 O(n log n)空间复杂度O(1)原地排序不符合题目要求 O(n)。如果使用计数排序或桶排序可以把时间降到O(n)但空间又要O(n)。所以这个直觉方案在面试题面前是错的。1.2 为什么排序和哈希表都不合格题目很硬性时间复杂度O(n)空间复杂度O(1)。这两个条件同时满足才是这道题真正的考点。很多人觉得空间O(n)没多大事但在大厂面试中这是区分“会写代码”和“理解了算法本质”的分水岭。面试官往往不会直接说“你空间超了”而是追问“还能不能更省空间”如果你只会哈希表这道题就卡住了。哈希表的思路用Set存所有元素然后从1开始循环看 hashSet.contains(i)不包含就返回i。时间O(n)空间O(n)。这其实是“时间换空间”的典型可惜这里要求空间常数。还有“标记数组”也一样开一个长度为n1的bool数组本质一样。那有没有办法做到时间O(n)、空间O(1)呢有而且不止一种。核心是利用“原数组的索引和正负号”作为额外的存储空间。换句话说我们不需要真的开一个新数组可以把原数组本身当成一张哈希表。这就是“原地哈希”思路。你可以把这道题看作是垃圾桶里捡宝贝地上已经有n个位置1到n这些数如果能出现就应该出现在它们对应的位置。谁没站在自己的位置谁就是缺失项。2. 核心洞察答案永远不会超过n12.1 抽屉原理与范围收缩在动手写代码之前先想清楚一个数学事实一个长度为 n 的数组缺失的第一个正数一定在 [1, n1] 这个区间里。为什么用抽屉原理解释数组有 n 个位置最多只能放下 n 个不同的正整数。如果1到n这n个数全都出现在数组里那么数组里就全是1到n这种情况下缺失的正数是 n1如果1到n中某个数k缺失那么答案就是那个最小的k显然k在1到n之间。所以无论怎样答案不会超过 n1。这个结论极其重要它把无限的问题收缩到了有限的范围。既然答案只和1到n有关那么数组中其他值负数、0、大于n的数都“不配参与讨论”可以直接忽略。这为原地置换法铺平了道路。可以类比成有 n 个坑位编号1到n每个坑位理论上应该蹲一个对应编号的萝卜。现在地上一堆萝卜数组元素有些萝卜的编号在1到n有些是烂萝卜负数、太大。我们只需要把编号在1到n的萝卜捡起来放到对应的坑位里最后看看哪个坑位是空的空坑对应的编号就是答案。2.2 原地置换的思路雏形让每个数回到“它该待的坑位”如何利用这个结论最朴素的想法如果数字 x 在数组里而且 1 x n那么它“应该”出现在索引 x-1 的位置上。这是因为数组下标从0开始数字1应该在下标0处数字2应该在下标1处以此类推。于是我们遍历数组当发现某个位置的数字不是它该有的数字时就把它交换到它该去的位置。交换后当前位置可能会得到一个“新数字”所以我们不能简单i而是要继续处理当前位置直到当前位置的数字不满足交换条件为止。经典例子nums [3, 4, -1, 1]n4。 i0nums[0]3它应该在索引2。把索引0和索引2交换得到 [-1, 4, 3, 1]。 此时i0的值是-1不在[1, n]忽略i。 i1nums[1]4应该在索引3。交换索引1和索引3得到 [-1, 1, 3, 4]。 此时i1的值是1应该在索引0。交换索引1和索引0得到 [1, -1, 3, 4]。 i1的值为-1忽略i。 i2nums[2]3等于i1正确i。 i3nums[3]4等于i1正确结束。最终扫描数组位置0是1正确位置1是-1不等于2所以缺失的最小正数是2。这个过程非常直观。这里有一个隐藏细节交换到当前位置的新值也可能满足交换条件所以必须用 while 而不是 if否则就会漏处理。我见过很多人写if然后测试用例不过。另外如果当前值和目标位置的值相同比如 [1,1] 这种重复数字交换就陷入死循环所以还得加一个“相等就跳出”的保护。这两个细节是这道题最容易出Bug的地方。3. 手撕实现一原地置换法3.1 交换逻辑详解与伪代码现在把上面思路落地成伪代码。对整个数组做一次循环但在循环体内用 while 处理“交换到正确位置”的操作for i in 0..n-1: while nums[i] 在 [1, n] 内: target_index nums[i] - 1 if nums[i] nums[target_index]: break swap(nums[i], nums[target_index])为什么第一个条件就可以保证 target_index 不越界因为此时 nums[i] 在1到n之间减1后是0到n-1正好是合法下标。为什么需要 nums[i] nums[target_index] 就 break假设 n2nums[1,1]。遍历到i1nums[1]1target_index0nums[0]1。如果交换两个数还是1位置不变循环永远无法结束。加一个相等判断直接跳过重复数字因为它已经出现过了不需要再处理。那会不会漏掉某些数字不会。比如 nums[1,1]第一个1在正确位置第二个1是重复值不影响答案。因为答案只关心“有没有出现过”重复出现不改变缺失情况。交换的次数是有限的。每次交换都会把一个数放到它最终应该在的位置最多交换 n 次所以总时间复杂度仍然是 O(n)。3.2 Python与Java代码实现写Python版本时注意Python支持多重赋值但如果在交换前有重复值判断可以直接用 Python 的 a,bb,a。但为了安全也可以写成临时变量。完整代码def firstMissingPositive(nums): n len(nums) for i in range(n): while 1 nums[i] n: target_pos nums[i] - 1 if nums[target_pos] nums[i]: break nums[i], nums[target_pos] nums[target_pos], nums[i] for i in range(n): if nums[i] ! i 1: return i 1 return n 1Java版本class Solution { public int firstMissingPositive(int[] nums) { int n nums.length; for (int i 0; i n; i) { while (nums[i] 1 nums[i] n) { int targetPos nums[i] - 1; if (nums[targetPos] nums[i]) { break; } int temp nums[i]; nums[i] nums[targetPos]; nums[targetPos] temp; } } for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } return n 1; } }注意Java里 while 循环中的条件不能写成 nums[i] ! i1因为可能在交换后仍满足其他条件。最好直接用范围判断 目标位置判断。这样写能规避不少隐性问题。3.3 复杂度与边界条件时间上每个被交换的数字都会到达它的最终位置之后不会再动。比如数字3被换到索引2之后不会再被换出去因为只有当遍历到索引2且值不是3时才会交换而此时值是3不会交换。所以整体交换次数最多n次时间复杂度O(n)。空间O(1)只用了常数变量。边界条件空数组n0第一个循环不执行第二个循环不执行返回 n1 1。正确。单元素数组 [1]循环处理while 11target_pos0nums[0]nums[0]break。第二次扫描发现nums[0]1正确返回2。正确。单元素 [2]n1while 条件 2 1 不成立所以不会进入第二次扫描返回1。正确。全是负数while条件不成立二次扫描返回1。正确。现场手撕时可以先和面试官确认“可以修改原数组吗”通常可以如果不能需要不同的解法。这道题题目没有说不可修改默认可以。4. 手撕实现二负号标记法哨兵优化4.1 为什么需要哨兵n1除了原地置换面试官还可能希望你掌握另一种经典解法负号标记法。这个思路更隐晦但面试中一旦你能写出两种解法绝对是加分项。核心思想用数组下标本身记录“哪些正数出现过”。比如一个位置如果是负数代表“这个位置对应的数字出现过”。怎么做到先把数组里所有不符合条件的数字小于等于0、大于n的统一替换成一个“哨兵”这个哨兵就是 n1。因为哨兵大于n不会影响“下标范围”内的任何数字。替换完以后整个数组所有元素都是正数。然后遍历数组遇到一个数字 x abs(nums[i])如果 x 在 1 到 n 之间就把下标 x-1 位置的数字改成负数保留绝对值。这样当一个位置是负数时就说明数字 index1 在数组中出现过。最后我们找到第一个仍为正数的位置这个位置对应的数字没出现过返回 index1如果全部都是负数说明 1 到 n 都出现过返回 n1。为什么不能直接把不在范围内的数变成0因为后面我们要用“负号”标记0既不是正也不是负影响判断。所以选一个正整数哨兵最合适。4.2 标记过程与完整代码用 [3,4,-1,1] 演示n4第一步把 -1 变成 5n1数组变为 [3,4,5,1]。第二步遍历 i0x3将下标2的数字5变为 -5数组变为 [3,4,-5,1]。 i1x4将下标3的数字1变为 -1数组变为 [3,4,-5,-1]。 i2xabs(-5)55n忽略。 i3xabs(-1)1将下标0的数字3变为 -3数组变为 [-3,4,-5,-1]。第三步扫描下标0是负数说明1出现过下标1是正数4说明2没出现过返回2。完整代码def firstMissingPositive(nums): n len(nums) for i in range(n): if nums[i] 0 or nums[i] n: nums[i] n 1 for i in range(n): x abs(nums[i]) if 1 x n: nums[x - 1] -abs(nums[x - 1]) for i in range(n): if nums[i] 0: return i 1 return n 1Java对应代码类似注意取绝对值要处理极端值Integer.MIN_VALUE不会因为我们第一步先把所有非正数变为n1所以后续遇到的值要么是原来的正数要么是被改成负号的正数绝对值。取abs安全。4.3 两种方案的对比与选型建议对比维度原地置换法负号标记法核心动作把数字交换到目标位置用正负号做布尔标记修改范围可能交换多次每个元素最多改一次代码量稍长有while和swap三段for代码更规整死循环风险有需处理重复值无直观程度容易理解需要绕一下面试推荐首选加分项我面试时通常会先说原地置换法因为“把数放到该在的位置”比较好向面试官解释。如果面试官追问“还有没有其他解法”再写负号标记法展示自己的知识面。需要注意负号标记法第二步用 -abs 修改时如果某个位置已经被标记为负再遇到同一个数时abs(负数)取回正数仍可以重复标记为负。这个细节很关键很多人直接写成 nums[x-1] -nums[x-1]如果已经是负数又变回正数导致后续结果错乱。一定要用 -abs。5. 面试现场的追问与避坑指南5.1 面试官高频追问题汇总这块是文章最有价值的部分。面试官除了让你写代码会疯狂抛出各种衍生问题考察你到底是背题还是真懂。复盘下来至少这几个问题出现过第一“为什么答案不会超过n1”这个问题其实就是考“抽屉原理”你要能从“n个位置最多容纳n个正整数”推导。答不上来面试官会怀疑你只是背了答案。第二“如果数组里全是负数或者零你的算法还能工作吗”能。原地置换法的while条件直接跳过负号标记法的第一步把它们变成n1最后扫描返回1。现场最好举个小例子比如 [ -5, 0, -2 ]走一遍流程。第三“如果存在重复数字比如 [1,1,2]怎么办”重复数字不会影响缺失正数的判断。原地置换法里重点处理相等值防死循环负号标记法重复标记同一个位置也无所谓。要明确指出我们只需要知道“有没有”不需要知道次数。第四“能不能用哈希表但是做到O(1)空间”这其实是诱导题。直接回答不能哈希表本身需要O(n)空间。但我们可以把原数组改造成哈希表也就是原地哈希这就是本题的考点。第五“如果要求不能修改原数组你怎么做”这题就变成另一种思路了。可以用分块bucket思想比如把n个元素分成若干个桶每个桶维护一个范围但要牺牲一些时间。面试中你可以先承认“题目未禁止修改所以原地修改是最优解法”再补充“如果禁止修改需要额外空间或者更复杂的分块现场我先不展开”。诚实的边界意识反而加分。5.2 手撕时最容易犯的5个错误我在模拟面试群看到很多同学写这题翻车最典型的错误有这几个错误一交换循环写成 if。如果当前位置交换进来一个新数字这个新数字可能也需要交换所以必须是 while。写 if 会导致类似 [3,4,-1,1] 返回错误答案。错误二忘记处理重复值导致死循环。比如 [1,1]两个1都在“合法范围”如果不判断 nums[i] nums[target_pos]while 将永远交换相同的两个数程序直接卡死。有些面试环境不设超时你会非常尴尬。错误三第二遍扫描时返回值写成 i。数组下标和数字差1记住应该是 i1。这个错误常见于紧张的时候。错误四负号标记法的第二步写成 nums[x-1] -nums[x-1]没有用 abs。当该位置已经是负数时会变成正数导致错判。正确写法是取当前绝对值再加负号。错误五在负号标记法第一步中没有把 0 替换掉。0 在正负号判断中会被认为是“非负”后续如果 x 指向这个位置取负后还是负数虽然可能不影响结果但0会被当成正数假设 nums [0,1]n2把0变成3数组[3,1]标记1将索引0位置3改成-3最后扫描下标0是负下标1是正返回2。如果0不替换[0,1]标记1索引0位置是00既不是正也不是负最后扫描时判断 nums[0] 0 为false不影响结果但第二次遍历可能 x0时不会标记。但0本身可以影响后面的判断如果x1nums[x-1]nums[0]00取负还是0“是否已经标记”无法区分。所以最好把非正数统一变成哨兵避免歧义。5.3 测试用例驱动的调试思路面试中写完代码不要急着让面试官看自己先在脑子里跑几个用例这样既能发现bug也能展现严谨。强烈建议把这几个用例记在脑子里空数组 []返回1。只有一个数且是[1]返回2。只有一个数且是[2]返回1。标准混合 [3,4,-1,1]返回2。连续完整 [1,2,3,4]返回5。带零和负数 [1,2,0]返回3。重复数字 [1,1]返回2。全负 [-1,-2,-3]返回1。全大数 [4,5,6]返回1。你可以从这组用例中挑三四个比如 [1,1] 检查死循环[4,5,6] 检查大于n的情况[3,4,-1,1] 检查核心交换。走一遍后代码基本稳了。我当时面试时写完原地置换法后主动说道“我可以再跑两个用例吗比如 [3,4,-1,1] 和 [1,1]。”面试官点头我就快速在草稿上推演。这个动作虽然简单但在面试官眼里代表你具备“测试”意识很多人会忽略。另外还有一个细节如果面试用白板面试不开IDE代码写完后自己默读一遍检查所有下标是否可能越界。特别是 while 循环里因为 nums[i] 变化了要确保 target_pos 每次都合法。有了 range 条件就不会越界。6. 扩展思考与个人心得6.1 这道题的变体与同类题掌握了核心思路很多变形题都能秒懂。比如“找到所有数组中消失的数字”那道题也是利用“原地哈希”把出现的数字对应位置标负最后值为正的下标就是缺失。对比两者差异在于本题只找最小的缺失正数消失的数字题要找全部缺失。所以本题的结论是“答案最多n1”而消失数字题只关心1到n中有谁缺失。类似的还有“重复数”问题比如“长度为n1的数组元素范围1到n找出重复的那个数”这类题可以用快慢指针也可以用原地标记。但要注意如果题目要求“不能修改数组”就会转向二分或位运算。6.2 面试策略如何把一道原题答出亮点这道题本身是原题面试官已经见过太多背答案的人。想拿高分你要做到三点。第一主动讲清复杂度。不要等面试官问写之前就说“我准备用原地置换法时间复杂度O(n)空间O(1)因为每次交换都会把一个数字放到最终位置总交换次数不超过n。”这句话一出来面试官就知道你真懂。第二主动聊边界条件。空数组、负数、重复值、全大数这些边界点提一遍能预防很多低级错误也展示出你的工程思维。第三不要只会一种解法。在面试末尾如果还有时间可以说“这种负号标记法也能做核心区别是……”。我当时就补充了第二种解法明显看到面试官眼神亮了一下。在准备这类题时我的个人经验是不要急着刷题先把“哈希”、“双指针”、“原地操作”、“单调栈”这些通用范式吃透。因为Hot 100里很多题都是同一套思路换了个壳你今天死记第41题明天换成“消失的数字”又不会了那就亏大了。写到最后再说一个小技巧面试时如果一时想不起某个边界可以把例子写出来。比如写 nums[2,1,0]手动推到 [1,2,0] 再扫描。推演的过程不仅帮你理清逻辑还能缓解卡壳的尴尬。我自己在多次模拟面试里验证过这个方法比干想有效得多。