原地哈希：数组自己就是哈希表

一句话结论（30s）

原地哈希的本质是”数组下标 = 哈希位置”，因为当数据范围限定在 1~n 时，把每个数交换到下标 x-1 处，就能用 O(1) 额外空间定位每个数该在的位置，省掉额外哈希表的 O(n) 空间。

核心原理（2min）

遍历数组，遇到在 [1, n] 范围内的数就把它交换到索引 nums[i]-1，直到该位置正确；一轮后第一个 nums[i] != i+1 的位置 i+1 即缺失数。用 while 而非 if，是为了把交换来的新数也继续归位，均摊 O(n)。

底层深入（5-10min）

问题：找出缺失的第一个正整数

给一个未排序的整数数组，找缺少的最小的正整数。O(n) 时间，O(1) 空间。

核心洞察

如果数组中有数字 x（1 ≤ x ≤ n），把 x 放到索引 x-1 的位置。一轮遍历后，第一个满足 nums[i] != i+1 的位置 i+1 就是缺失的第一个正整数。

为什么能这么”理所当然”地拿索引当哈希位？ 因为数据范围 1~~n 和下标 0~~n-1 恰好差 1，二者是一一对应关系；既然位置信息已经免费存在，就无需再开一个哈希表去存”每个数该在哪”——这就是”原地”的由来。

💭 思考：看到什么信号该想到”原地哈希”？——题目同时给两个约束：数据范围被限定在 1~~n（与数组大小相关）、且要求 O(1) 额外空间。额外哈希表要 O(n) 空间被砍掉后，只剩数组本身可用，而”下标 0~~n-1”恰好能一一对应”值 1~n”，于是”数组当哈希表”的想法自然冒出来。先看范围、再看空间约束，两者对上，原地哈希就是默认答案。

int firstMissingPositive(int[] nums) {
    int n = nums.length;
    // 1. 将每个数放到它的"正确位置"
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);  // 交换到正确位置
        }
    }
    // 2. 找第一个位置不对的数
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;  // 全对 → 缺失 n+1
}

为什么 while 不是 if：交换后新的 nums[i] 可能是另一个在 [1, n] 内的数，需要继续把它也放到正确位置。每交换一次，至少有一个数到达正确位置，最多交换 n 次——均摊 O(n)。不这样会怎样？ 用 if 只换一次，刚换过来的那个数可能仍不在正确位置，就永远没人管它了，最终会漏判缺失数。

为什么时间复杂度仍是 O(n)？

每个数最多被交换一次就到达正确位置。while 的每次迭代产生一次 exchange，exchange 的总次数 ≤ n（每个位置被修正一次）。二重循环但操作数有限——O(2n) = O(n)。

💭 思考：看着是二重循环，为什么敢说均摊 O(n)？——别被 while 吓到，数的是”交换次数”：每交换一次，至少有一个数被放到了它的正确位置，而”正确位置”总共只有 n 个，所以交换总次数 ≤ n。内层 while 看似会跑很多轮，但把全过程的交换次数加起来是有上限的——这就是”均摊分析”，用”总工作量/操作数”看复杂度，而不是单看某一次循环。

扩展：找出所有消失的数字

1~n 中有一些数出现了两次，导致一些数缺失。同样是原地哈希：把出现的数放到对应索引，索引+1 不等于 nums[i] 的位置 = 缺失数。

💭 思考：为什么”缺失数”类题也能套同一个模板？——“出现两次导致缺失”的题，本质还是”值该待在哪”的问题：值 x 就该在索引 x-1。只要把范围限定在 1~n、且关心的位置信息都在下标里，不管问”第一个缺失”还是”所有缺失”，都是归位后再扫一遍找 nums[i] != i+1 的位置。抓住”下标=值的位置”这个不变量，一类题共用一套代码。

总结

原地哈希利用了”数组的索引天然是哈希表”——把”查找元素的哈希位置”转化为”交换到对应索引”。当数据范围与数组大小相关时（如 1~n），可以直接用数组索引编码位置信息，省去额外哈希表的 O(n) 空间。

章末提问

为什么这类题能不用额外哈希表，做到 O(1) 空间？ 结论：因为数据范围被限定在 1~~n，与下标 0~~n-1 一一对应，数组自己就能当哈希表；把每个数交换到 nums[i]-1 处即可”原地”记录存在性。
交换循环为什么要用 while 而不是 if？ 结论：因为交换一次后，nums[i] 上的新数可能仍在 [1,n] 内且位置不对，必须继续把它归位；用 if 会漏掉这个新换来的数。
这个 while 为什么均摊还是 O(n)？ 结论：因为每次交换都让至少一个数到达正确位置，而正确位置总数不超过 n，所以总交换次数 ≤ n；二重循环但总操作数有限，整体 O(n)。

原地哈希——把数组本身当成哈希表