空间找缺失)
给你一个未排序的整数数组找出其中没有出现的最小的正整数。要求O(n)时间O(1)额外空间。不准排序O(nlogn)超时、不准开哈希集O(n)空间超标、更不准从1开始逐个in判断O(n²)。第一次遇到这道题的人多半会卡住——不记账怎么知道谁缺席了答案藏在一句几乎没人当回事的话里如果数组长度是n那么要找的那个正整数只可能是1到n1之间的某个数。因为它不可能是n2——那样1到n1这n1个数就都得塞进n个位置里鸽笼原理说不可能。既然答案就在[1, n]里打转而数组恰好有n个位置——那为什么不干脆让“值v”住在“下标v-1”这个房间里呢一旦这么想数组本身就变成了一张哈希表键是值槽位是下标而且天然无冲突。把每个值送回它的房间谁缺席、谁多余一眼就看出来了。这个手法叫循环排序cyclic sort也叫原地哈希in-place hashing。 题目速览30秒读懂题目1缺失的第一个正数LC.41未排序数组找出没有出现的最小正整数。O(n)时间 O(1)空间。示例[1,2,0]→3[3,4,-1,1]→2[7,8,9,11,12]→1题目2找到所有数组中消失的数字LC.448延伸含n个整数nums[i] ∈ [1,n]找出所有在[1,n]范围内但没有出现的数字。O(n)时间 不用额外空间。示例[4,3,2,7,8,2,3,1]→[5,6][1,1]→[2]两题一脉相承LC.41找第一个缺席的LC.448找所有缺席的。连模板都几乎是同一份唯一差别第四节会点破。 核心思路下标即哈希核心洞察一张普通哈希表要做三件事算哈希值、解决冲突、扩容。而这里全都不需要——因为键的集合[1, n]里的整数和槽位的集合0到n-1的下标是同一个集合的两个名字。于是“插入”退化成了一次交换值v的家是下标v - 1从左到右扫只要当前位置i上的数nums[i]是合法值落在[1, n]而且它的家里住的不是它自己就把这两个位置交换——一次交换至少让一个元素永久归位。⚠️ 那个最容易写错的while条件模板长得人畜无害但while的判定条件写错会直接死循环# ❌ 错误写法while1nums[i]nandnums[i]!i1:swap(nums[i],nums[nums[i]-1])# ✅ 正确写法while1nums[i]nandnums[nums[i]-1]!nums[i]:swap(nums[i],nums[nums[i]-1])区别在哪用nums [2, 2]试一遍就明白了错版i0nums[0]2 ≠ 1交换nums[0]和nums[1]。可两个位置都是2交换完还是[2, 2]——条件依然成立无限循环。正版i0nums[0]2它的家是nums[1]而nums[1]已经等于2了条件为假循环直接跳过。0次交换答案就是1位置0上住的应该是1却是2。判据的本质区别nums[i] ! i1问的是“我这个位置对不对”而nums[nums[i]-1] ! nums[i]问的是“我家里住的是不是我自己”。重复值场景下前者永远为真、后者一次为假。本机实测错版在[2,2]上会无限交换正版0次交换直接出答案。LC.41 多了哪一步LC.448 的输入保证值域在[1, n]可以无条件归位。但LC.41的输入有负数、0、以及大于n的数——这些数没有家下标会越界必须跳过。这就是1 nums[i] n这个范围判断存在的理由也是两题模板的唯一差异。为什么整体是O(n)while看起来像嵌套循环容易被误判成O(n²)。但每一次交换都让至少一个元素永久地回到了它的家而每个元素一生只回家一次所以所有while迭代加起来不超过n次。外层n次 内层总共 ≤ n次 O(n)。本机跑了3000组随机用例n ≤ 40统计到的最大交换次数是26始终没有超过数组长度——与论证一致。️ 图解算法手把手走一遍nums [3, 4, -1, 1]n 4答案2。归位阶段步骤inums[i]它的家动作归位后数组103nums[2] -1 ≠ 3交换nums[0]与nums[2][-1, 4, 3, 1]20-1不在[1,4]跳过—[-1, 4, 3, 1]314nums[3] 1 ≠ 4交换nums[1]与nums[3][-1, 1, 3, 4]411nums[0] -1 ≠ 1交换nums[1]与nums[0][1, -1, 3, 4]51-1不在[1,4]跳过—[1, -1, 3, 4]623nums[2] 3已在家—[1, -1, 3, 4]734nums[3] 4已在家—[1, -1, 3, 4]扫描阶段下标 i期望i1实际nums[i]对不对011✅12-1❌第一个错位233✅344✅第一个错位在下标1所以答案是1 1 2✓ 代码实现Python JavaPython版classSolution:# ---------- LC.41 缺失的第一个正数 ----------deffirstMissingPositive(self,nums:list[int])-int:nlen(nums)foriinrange(n):# 条件一值必须在[1, n]否则没有家# 条件二它的家里住的不是它自己重复值时直接为假防死循环while1nums[i]nandnums[nums[i]-1]!nums[i]:jnums[i]-1nums[j],nums[i]nums[i],nums[j]foriinrange(n):ifnums[i]!i1:returni1# 第一个住错号的位置returnn1# 1..n全到齐# ---------- LC.448 找到所有数组中消失的数字 ----------deffindDisappearedNumbers(self,nums:list[int])-list[int]:# 输入保证值域在[1, n]不需要范围判断——与 LC.41 唯一差异foriinrange(len(nums)):whilenums[nums[i]-1]!nums[i]:jnums[i]-1nums[j],nums[i]nums[i],nums[j]return[i1fori,vinenumerate(nums)ifv!i1]Java版classSolution{publicintfirstMissingPositive(int[]nums){intnnums.length;for(inti0;in;i){while(nums[i]1nums[i]nnums[nums[i]-1]!nums[i]){intjnums[i]-1;inttmpnums[j];nums[j]nums[i];nums[i]tmp;}}for(inti0;in;i){if(nums[i]!i1)returni1;}returnn1;}publicListIntegerfindDisappearedNumbers(int[]nums){intnnums.length;for(inti0;in;i){while(nums[nums[i]-1]!nums[i]){intjnums[i]-1;inttmpnums[j];nums[j]nums[i];nums[i]tmp;}}ListIntegerresnewArrayList();for(inti0;in;i){if(nums[i]!i1)res.add(i1);}returnres;}}⚠️防坑提醒必看while第二个条件必须是nums[nums[i]-1] ! nums[i]写成nums[i] ! i1在[2,2]上会死循环。这是本篇头号陷阱。LC.41 必须带范围判断LC.448 可以不带——别把两版模板混着抄。答案可能是n1别漏掉最后那行return n 1。[1,2,3]的答案是4。⏱️ 复杂度分析面试必问题目时间空间说明LC.41O(n)O(1)外层n次内层交换总次数 ≤ nLC.448O(n)O(1)同上解法时间空间评价排序后扫描O(nlogn)O(1)❌ 违反线性时间哈希集记账O(n)O(n)❌ 违反常数空间从1开始逐个inO(n²)O(1)❌ 太慢循环排序O(n)O(1)✅ 正解⚠️ 但“O(1)空间”不等于“更快”这是本周第一个反直觉结论。本机对比CPython 3.13实现n 10⁵n 10⁶额外空间循环排序原地哈希24.23ms342.09msO(1)哈希集5.04ms74.88msO(n)原地哈希慢了4~5倍。原因哈希集的in是C层实现的一次哈希查找而循环排序的每次归位都是Python解释器层的多次数组读写加交换。常数差得太远量级都是O(n)补不回来。面试正确姿势面试官要O(1)空间你就写循环排序并且能讲清复杂度但真实工程里求快且内存不是瓶颈哈希集往往更好。先确认你要优化的是哪个指标再动手。 举一反三5道高频变体题题号题目与本题的关系LC.442数组中重复的数据同一次归位的另一半答案LC.287寻找重复数循环排序能做但题面禁止改数组LC.268丢失的数字[0,n]里缺一个可用异或或求和LC.645错误的集合LC.442 找缺失一次归位拿到两个答案LC.765情侣牵手循环排序的“配对”版本 面试追问模拟提前准备惊艳全场Q1为什么不会有哈希冲突因为键的集合与槽位的集合是同一个集合。普通哈希表要处理冲突是因为键空间远大于槽位空间而这里[1,n]到[0,n-1]是完美的一一对应每个值有且仅有一个家。这是它比真哈希表更强的地方也是它只能用在“值域恰好等于下标域”这个窄场景的原因。Q2内层while为什么总共只跑O(n)次每次进入while循环体都会执行一次交换而每次交换都让至少一个元素永久归位。一个位置一旦归位就不会再被换走后续while条件会为假所以交换次数 ≤ n。Q3如果数组里有重复值怎么办正好由nums[nums[i]-1] ! nums[i]这个条件接住。重复值意味着“两个相同的值抢同一个房间”第二个到达时发现家里已经住了自己人于是留在原地不动最后扫描阶段就会被认出来LC.442正是靠这一点找重复数。Q4LC.41 能不能用取反标记法做能但更绕需要先把非正数统一成哨兵值再逐位取反标记最后还要还原。既然归位法已经能O(n)/O(1)解决就没必要绕这一圈。但当元素不能交换位置时比如每个位置挂着额外数据取反标记法就是唯一选择。 实战小技巧刷题党必备口诀值v的家是下标v−1一次交换归位一个归位完成后谁住错号就是答案。模板while 1nums[i]n and nums[nums[i]-1]!nums[i]: swap。防坑第二个条件用nums[nums[i]-1] ! nums[i]不是nums[i] ! i1LC.41 别忘范围判断答案可能是n1。 实际应用场景不止是刷题数据完整性校验一批编号本应连续1到n的记录用O(1)空间找出断了哪几号内存受限的嵌入式场景无法分配辅助数组时的查缺补漏置换的分解循环排序本质上是在分解一个置换的循环节这个视角在全排列里还会出现 今日思考题本篇实测发现“原地哈希O(1)空间反而比哈希集O(n)空间慢4~5倍”。你在工作中有没有遇到过“为了满足空间要求反而把程序写慢了”的情况最后是怎么取舍的
