空间找缺失)
给你一个未排序的整数数组，找出其中没有出现的最小的正整数。
要求：O(n)时间，O(1)额外空间。
不准排序（O(nlogn)超时）、不准开哈希集（O(n)空间超标）、更不准从1开始逐个in判断（O(n²)）。
第一次遇到这道题的人多半会卡住——不记账，怎么知道谁缺席了？
答案藏在一句几乎没人当回事的话里：如果数组长度是n，那么要找的那个正整数只可能是1到n+1之间的某个数。
因为它不可能是n+2——那样1到n+1这n+1个数就都得塞进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的判定条件写错会直接死循环：
# ❌ 错误写法while1<=nums[i]<=nandnums[i]!=i+1:swap(nums[i],nums[nums[i]-1])# ✅ 正确写法while1<=nums[i]<=nandnums[nums[i]-1]!=nums[i]:swap(nums[i],nums[nums[i]-1])区别在哪？用nums = [2, 2]试一遍就明白了：
- 错版：
i=0，nums[0]=2 ≠ 1，交换nums[0]和nums[1]。可两个位置都是2，交换完还是[2, 2]——条件依然成立，无限循环。 - 正版：
i=0，nums[0]=2，它的家是nums[1]，而nums[1]已经等于2了，条件为假，循环直接跳过。0次交换，答案就是1（位置0上住的应该是1，却是2）。
判据的本质区别：nums[i] != i+1问的是“我这个位置对不对”，而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）。
归位阶段
| 步骤 | i | nums[i] | 它的家 | 动作 | 归位后数组 |
|---|---|---|---|---|---|
| 1 | 0 | 3 | nums[2] = -1 ≠ 3 | 交换nums[0]与nums[2] | [-1, 4, 3, 1] |
| 2 | 0 | -1 | 不在[1,4]，跳过 | — | [-1, 4, 3, 1] |
| 3 | 1 | 4 | nums[3] = 1 ≠ 4 | 交换nums[1]与nums[3] | [-1, 1, 3, 4] |
| 4 | 1 | 1 | nums[0] = -1 ≠ 1 | 交换nums[1]与nums[0] | [1, -1, 3, 4] |
| 5 | 1 | -1 | 不在[1,4]，跳过 | — | [1, -1, 3, 4] |
| 6 | 2 | 3 | nums[2] = 3，已在家 | — | [1, -1, 3, 4] |
| 7 | 3 | 4 | nums[3] = 4，已在家 | — | [1, -1, 3, 4] |
扫描阶段
| 下标 i | 期望i+1 | 实际nums[i] | 对不对 |
|---|---|---|---|
| 0 | 1 | 1 | ✅ |
| 1 | 2 | -1 | ❌第一个错位 |
| 2 | 3 | 3 | ✅ |
| 3 | 4 | 4 | ✅ |
第一个错位在下标1，所以答案是1 + 1 = 2✓
💻 代码实现（Python + Java）
Python版
classSolution:# ---------- LC.41 缺失的第一个正数 ----------deffirstMissingPositive(self,nums:list[int])->int:n=len(nums)foriinrange(n):# 条件一：值必须在[1, n]，否则没有"家"# 条件二：它的家里住的不是它自己（重复值时直接为假，防死循环）while1<=nums[i]<=nandnums[nums[i]-1]!=nums[i]:j=nums[i]-1nums[j],nums[i]=nums[i],nums[j]foriinrange(n):ifnums[i]!=i+1:returni+1# 第一个"住错号"的位置returnn+1# 1..n全到齐# ---------- LC.448 找到所有数组中消失的数字 ----------deffindDisappearedNumbers(self,nums:list[int])->list[int]:# 输入保证值域在[1, n]，不需要范围判断——与 LC.41 唯一差异foriinrange(len(nums)):whilenums[nums[i]-1]!=nums[i]:j=nums[i]-1nums[j],nums[i]=nums[i],nums[j]return[i+1fori,vinenumerate(nums)ifv!=i+1]Java版
classSolution{publicintfirstMissingPositive(int[]nums){intn=nums.length;for(inti=0;i<n;i++){while(nums[i]>=1&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){intj=nums[i]-1;inttmp=nums[j];nums[j]=nums[i];nums[i]=tmp;}}for(inti=0;i<n;i++){if(nums[i]!=i+1)returni+1;}returnn+1;}publicList<Integer>findDisappearedNumbers(int[]nums){intn=nums.length;for(inti=0;i<n;i++){while(nums[nums[i]-1]!=nums[i]){intj=nums[i]-1;inttmp=nums[j];nums[j]=nums[i];nums[i]=tmp;}}List<Integer>res=newArrayList<>();for(inti=0;i<n;i++){if(nums[i]!=i+1)res.add(i+1);}returnres;}}⚠️防坑提醒（必看）：
while第二个条件必须是nums[nums[i]-1] != nums[i]，写成nums[i] != i+1在[2,2]上会死循环。这是本篇头号陷阱。- LC.41 必须带范围判断，LC.448 可以不带——别把两版模板混着抄。
- 答案可能是
n+1，别漏掉最后那行return n + 1。[1,2,3]的答案是4。
⏱️ 复杂度分析（面试必问）
| 题目 | 时间 | 空间 | 说明 |
|---|---|---|---|
| LC.41 | O(n) | O(1) | 外层n次，内层交换总次数 ≤ n |
| LC.448 | O(n) | O(1) | 同上 |
| 解法 | 时间 | 空间 | 评价 |
|---|---|---|---|
| 排序后扫描 | O(nlogn) | O(1) | ❌ 违反线性时间 |
| 哈希集记账 | O(n) | O(n) | ❌ 违反常数空间 |
从1开始逐个in | O(n²) | O(1) | ❌ 太慢 |
| 循环排序 | O(n) | O(1) | ✅ 正解 |
⚠️ 但“O(1)空间”不等于“更快”
这是本周第一个反直觉结论。本机对比（CPython 3.13）：
| 实现 | n = 10⁵ | n = 10⁶ | 额外空间 |
|---|---|---|---|
| 循环排序（原地哈希） | 24.23ms | 342.09ms | O(1) |
| 哈希集 | 5.04ms | 74.88ms | O(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正是靠这一点找重复数）。
Q4：LC.41 能不能用取反标记法做？
能，但更绕：需要先把非正数统一成哨兵值，再逐位取反标记，最后还要还原。
既然归位法已经能O(n)/O(1)解决，就没必要绕这一圈。但当元素不能交换位置时（比如每个位置挂着额外数据），取反标记法就是唯一选择。
🧩 实战小技巧（刷题党必备）
- 口诀：值v的家是下标v−1；一次交换归位一个；归位完成后谁住错号就是答案。
- 模板：
while 1<=nums[i]<=n and nums[nums[i]-1]!=nums[i]: swap。 - 防坑：第二个条件用
nums[nums[i]-1] != nums[i]，不是nums[i] != i+1；LC.41 别忘范围判断；答案可能是n+1。
📈 实际应用场景（不止是刷题）
- 数据完整性校验：一批编号本应连续（1到n）的记录，用O(1)空间找出断了哪几号
- 内存受限的嵌入式场景：无法分配辅助数组时的查缺补漏
- 置换的分解：循环排序本质上是在分解一个置换的循环节，这个视角在全排列里还会出现
🎁 今日思考题
本篇实测发现“原地哈希（O(1)空间）反而比哈希集（O(n)空间）慢4~5倍”。
你在工作中有没有遇到过“为了满足空间要求，反而把程序写慢了”的情况？最后是怎么取舍的？
