答案是第一个缺失的正整数，通过原地哈希将1~n映射到下标0~n−1，遍历交换至正确位置后，首处nums[i]≠i+1的i+1即为答案，否则为n+1。
直接在原数组上做标记，把数字 1 到 n 映射到下标 0 到 n−1 的位置，再遍历一次找第一个“没被正确放置”的位置，就是答案。
核心思路：原地哈希（in-place hashing）
目标是 O(n) 时间、O(1) 空间。不能额外开布尔数组，也不能排序（会破坏 O(n)）。关键观察：
- 如果数组长度为 n，那么答案一定在区间 [1, n+1] 内；
- 若 1~n 全都出现，则答案是 n+1；否则答案是 1~n 中第一个缺失的数；
- 因此只需关注 1~n 这些数，并尝试把它们放到对应下标（即数字 x 放到索引 x−1 处）。
三步操作流程
遍历数组，对每个位置 i 做如下处理：
deep-java-review
下载
Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...
- 若当前值 nums[i] 是 1~n 范围内的正整数，且它还没在正确位置（即 nums[i] ≠ nums[nums[i]−1]），就把它交换到下标 nums[i]−1 处；
- 重复交换，直到当前位置的数要么超出范围，要么已在正确位置；
- 全部整理完后，再从头扫描：第一个满足 nums[i] ≠ i+1 的下标 i，答案就是 i+1；若全满足，答案是 n+1。
代码关键片段（Java）
// 假设 nums 非空
立即学习“Java免费学习笔记（深入）”；
int n = nums.length;
for (int i = 0; i
while (nums[i] >= 1 && nums[i]
int targetIdx = nums[i] - 1;
int temp = nums[targetIdx];
nums[targetIdx] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
注意边界与常见坑点
- 交换时必须检查 nums[nums[i]−1] != nums[i]，避免死循环（比如 [1,1] 中两个 1 相互交换）；
- 只处理 1~n 的数，负数、0、大于 n 的数一律跳过；
- while 循环内要更新 nums[i]，所以用 while 而不是 if；
- 数组可能含重复数，但不影响逻辑——只要 1~n 中某个数出现过，它最终会落到对应位置；重复的数会被“挤”到无效位置，后续扫描自然忽略。
