#41
困难
中频
原地哈希缺失的第一个正数
这是一道围绕数组、排序展开的高频练习。建议先掌握「原地哈希」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
排序
题目分析
给你一个无序整数数组，要求找出其中没有出现过的最小正整数。
题目还要求时间复杂度是线性的，并且额外空间复杂度是常数级。
比如 [1,2,0] 的答案是 3，[3,4,-1,1] 的答案是 2。
一句话概括：
把每个正整数尽量放回它应该在的位置，再找第一个没放对的位置。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：把值为
x 的正数尽量放到下标 x-1 的位置，最后第一个位置不对的地方就是缺失的最小正数。推荐代码
推荐解法：原地哈希
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 把值为
x 的正数尽量放到下标 x-1 的位置，最后第一个位置不对的地方就是缺失的最小正数。class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int correctIndex = nums[i] - 1;
int temp = nums[i];
nums[i] = nums[correctIndex];
nums[correctIndex] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用数组下标做原地哈希，把值放回它应该在的位置上。
核心过程
- 只关注
1到n范围内的正数，因为答案只可能在[1, n+1]。 - 遍历数组，把有效值
x放到下标x-1的位置。 - 整理完成后，从头扫描第一个错位位置。
- 如果全部都对，答案就是
n+1。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题最关键的转换是“把值和下标绑定起来”。
核心思路
最小缺失正数只和区间 [1, n+1] 有关。利用数组下标做原地哈希，把每个有效正数放回它应该在的位置后，再扫描错位点即可得到答案。
步骤讲解
1
把有效正数放回对应位置
当 nums[i] 在 [1, n] 范围内，且它不在自己应该去的位置时，就不断交换到 nums[nums[i]-1]。
为什么这样做：值和下标建立一一对应后，数组本身就成了哈希表。
对应代码提示：while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { ... }
2
从头扫描第一个错位位置
整理完成后，第一个不满足 nums[i] == i + 1 的位置，其缺失正数就是 i + 1。
为什么这样做：前面位置都正确，说明更小的正数已经全部存在。
对应代码提示：if (nums[i] != i + 1) return i + 1;
3
如果都对，答案就是 n+1
当 1 到 n 全都在正确位置时，最小缺失正数只能是 n+1。
为什么这样做：这是鸽巢原理下的自然补位结果。
对应代码提示：return n + 1;
易错点
试图处理所有整数
负数、0 和大于 n 的数都不可能影响答案位置。
正确理解：只关注
[1, n] 范围内的值。交换时没防止重复值死循环
若目标位置已经有同样的值，再交换会原地打转。
正确理解：循环条件里要加
nums[nums[i] - 1] != nums[i]。额外开哈希集合
虽然能做，但空间不是题目要求的 O(1)。
正确理解：优先使用数组下标原地建模。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比哈希集合更省空间，也满足题目对线性时间常数空间的要求。
适用判断：数组题里如果值域和下标都在同一量级，优先考虑原地哈希或循环置换。
额外提醒
- 真正重要的是把 1 到 n 放回家，其余值可以忽略。