缺失的第一个正数

排序太慢、哈希表太占地。我们得换个思路:让数组自己当哈希表。

n 个位置最多装下 1~n;装满了就缺 n+1,没装满就有个更小的缺口。负数、超 n 的数都没用。

约定数字 x 的家 = 下标 x−1。让每个数都搬回家,扫一遍就知道谁缺席了。

下面用 [3,4,-1,1,1] 一格一格演:cur 指针停在某格,该数能归位就交换,绿色 visited = 已到家。

i=0 · 看 3：cur 停在下标0,值是 3。它在 1~5 范围内,先看该回哪个家。

i=0 · 标家：3 该住下标2(家=x−1)。把目标家点亮:那里现在是 -1,两格准备交换。

i=0 · 交换后：交换发生!下标0 和下标2 的值真的互换了:3 回到下标2(变绿)。cur 还在下标0,新来的是 -1。

i=0 · 看 -1：cur 处现在是 -1,负数没有家,换不动了。这格变灰,cur 准备前进到下标1。

i=1 · 看 4：cur 移到下标1,值是 4。在范围内,看它该回哪个家。

i=1 · 标家：4 该住下标3。点亮目标家:那里现在是 1,两格准备交换。

i=1 · 交换后：下标1 和下标3 互换:4 回到下标3(变绿)。cur 仍在下标1,换来一个新的 1,还得继续看。

i=1 · 标家(连环)：cur 没动!换来的 1 也不在家,它该住下标0。点亮下标0——这就是为什么用 while:换来的新数接着归位。

i=1 · 交换后：再次交换:下标1 和下标0 互换,1 回到下标0(变绿)。cur 处又变回 -1。

i=1 · 看 -1：cur 处是 -1,换不动。下标1 这一轮结束,cur 前进到下标2。

i=2 · 看 3：cur 到下标2,值 3 早就在自己家了(之前归过位),无需交换,cur 前进。

i=3 · 看 4：cur 到下标3,值 4 也在自己家,跳过。只剩最后一格 1 没看。

i=4 · 看 1(重复)：cur 到最后一格下标4,又是个 1。它的家也是下标0,看看那里现在住着谁。

i=4 · 判等 · 停手：下标0 已经是 1!判等条件挡住了原地死循环,这个重复的 1 留在原地,停手。归位阶段结束。

归位完成 · 数组定型：归位定型:绿色是住对了家的,灰色是没人能归位的位置。下面第二趟从左扫,找第一个「下标 i 不住 i+1」的格子。

第二趟 · 准备扫描：归位完了,清空标记,从头开始第二趟:逐格问「下标 i 住的是 i+1 吗?」第一个不是的,就是缺口。

扫描 · 下标0：第二趟扫描开始。下标0 应该住 1,实际就是 1,对上了,cur 右移。

扫描 · 下标1 → 找到!：下标1 应该住 2,实际是 -1,对不上!第一个空家就是它 → 缺失的最小正数 = 2。

把数组自己当哈希桶,既没排序也没开表,时间空间双双卡到最优。

LC448(找所有消失的数)、LC442(找所有重复)、LC287(找重复数)都是这一招的变体。

雷区实演 · nums=[1,1]：换个最小反例 [1,1]:下标0 的 1 想回下标0,可那里本就是 1,值完全相同。

雷区实演 · 判等救场：判等条件 nums[nums[i]−1] != nums[i] 成立时就停手。漏掉它,这两个 1 会原地无限交换——这就是死循环命门。

边界三连：极端情形:全负、装满、有重复。三种都过,代码才算稳。

面试追问：把「O(n)」和「防死循环」讲透,是这道难题的面试分水岭。