缺失的第一个正数
First Missing Positive
找出数组中没有出现的最小正整数，要求时间 O(n)、空间 O(1)。
在力扣中练习题目描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
解题思路
主解法
原地哈希 · 值放回下标
值 v 应该待在下标 v-1
如果可以用哈希集合，先把所有正数装进去，再从 1 开始逐个查，答案立刻出来；但空间是 O(n)。
利用数组本身当下标表：值 v（1 ≤ v ≤ n）应该放在下标 v-1。遍历每个位置，如果当前值在范围内且目标位置不是同一个值，就交换过去，直到当前值无法归位。
自拟主例 [2,5,1,4,6]：2 换到下标 1，换来的 5 继续换到下标 4，最后 1 归位，数组变成 [1,2,6,4,5]。
分步图解
nums[0] = 2 属于下标 1，交换过去；第 1 次交换。
- i
- 0
- target
- 1
最后从下标 0 扫描，第一个 nums[i] != i+1 的位置，答案就是 i+1；都正确则返回 n+1。
图解
普通节点当前操作已确认 / 结果排除 / 冲突
每个数最多被交换到正确位置一次，时间 O(n)，空间 O(1)。
时间 O(n)空间 O(1)
易错点
- while 条件少了“目标位置值不同”：重复值会在两个位置之间无限交换。
- 只处理正数却忘了 <= n 的上界：nums[i] 可能远大于 n，会越界。
- 扫描时从 1 开始找值：应该检查 nums[i] 是否等于 i+1。
- 所有 1..n 都出现时忘记返回 n+1。
对照解法
哈希集合 · O(n) 空间
把所有数装进集合，从 1 开始逐个查
时间 O(n)，但需要 O(n) 额外空间；主解法利用数组本身当下标表，满足空间 O(1)。
最直观的做法：把数组元素放进哈希集合，然后从 1 开始依次问“在不在集合里”，第一个不在的就是答案。
时间 O(n)，空间 O(n)。它不受“值必须落在 1..n”的限制，思路简单，适合先写出正确版本。
- 1所有元素放入集合。
- 2candidate 从 1 开始。
- 3集合包含 candidate 就 ++candidate。
- 4返回 candidate。
时间 O(n)空间 O(n)
易错点
- 从 0 开始找：0 不是正整数，答案最小是 1。
- 只遍历原数组的最大值：如果 1..max 都出现，答案可能是 max+1。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
nums = [2,5,1,4,6]把 1..n 范围内的数尽量放回自己的位置：值 v 放到下标 v-1。
- n
- 5
查看 C++ 代码
延伸阅读
- “值 v 放到下标 v-1”是原地哈希的典型手法，也用于找到重复数、缺失数等问题。
- 如果题目不要求 O(1) 空间，哈希集合最稳；先写对再考虑压缩空间。