原地哈希的核心是将正整数n置于下标n-1处；遍历发现首个nums[i]≠i+1时，i+1即为答案；仅处理[1,n]内数字，遇重复值停止交换以防死循环。
用原地哈希把数字放到对应下标位置
核心思路是让每个正整数 n 尽可能出现在下标为 n-1 的位置（因为数组下标从 0 开始，而我们要找的是最小正整数）。这样遍历一遍就能发现第一个“名不副实”的位置：如果 nums[i] != i + 1，那 i + 1 就是答案。
操作时需注意边界和重复值：
- 只处理范围在
[1, n]内的数（n是数组长度），其余直接跳过 - 遇到重复值（比如
nums[i] == nums[nums[i]-1]）必须停止交换，否则死循环 - 交换后要重新检查当前下标，不能无脑
i++
for (int i = 0; i < n; ) {
int x = nums[i];
if (x >= 1 && x <= n && nums[x-1] != x) {
swap(nums[i], nums[x-1]);
} else {
i++;
}
}
遍历找第一个“缺位”的正整数
原地哈希完成后，数组满足：若 k ∈ [1,n] 存在，则必有 nums[k-1] == k。所以只需从头扫描：
- 遇到第一个
nums[i] != i + 1，立即返回i + 1 - 如果全匹配（即
nums[i] == i + 1对所有i成立），说明1到n都出现了，答案就是n + 1
这一步时间复杂度严格 O(n)，且不依赖额外空间。
立即学习“C++免费学习笔记（深入）”；
为什么不能用 set 或排序？
虽然 std::set 插入再遍历或先排序再扫描看起来更直觉，但它们有明显代价：
-
std::set带来O(n log n)时间和O(n)额外空间，还可能因重复插入导致逻辑绕弯 - 排序（如
std::sort）破坏原数组、引入O(n log n)，且去重逻辑需额外处理（比如unique后截断） - 题目隐含要求“常数额外空间”，原地哈希是唯一符合的解法
面试或 OJ 中若看到“不使用额外空间”“in-place”等提示，基本就是在引导你往这个方向想。
边界情况和易错点
实际写的时候最容易栽在几个细节上：
- 数组为空时直接返回
1—— 别忘了判空 - 数组含负数或大于
n的数，它们无法映射到有效下标，必须跳过，否则nums[x-1]越界 - 交换条件里漏掉
nums[x-1] != x，会导致无限循环（例如[1,1]） - 用
for (int i = 0; i 硬递增，会跳过交换后新到当前位置的非法值
真正难的不是算法本身，而是写对下标计算和交换终止条件——多手写两遍 nums[i] 和 i+1 的对应关系，比背模板管用。
