LeetCode 41困难数组 · 原地标记
缺失的第一个正数 图解题解
这道题到底在问什么
给一个未排序整数数组,找出其中没出现过的最小正整数。要求时间 O(n)、额外空间 O(1)。
- nums
- [3,4,-1,1,1]
- 输出
- 2
- 解释
- 1 在、2 不在 → 答案 2
最优解：一步一步想明白
- 3排序太慢、哈希表太占地。我们得换个思路:让数组自己当哈希表。
- 4n 个位置最多装下 1~n;装满了就缺 n+1,没装满就有个更小的缺口。负数、超 n 的数都没用。
- 5约定数字 x 的家 = 下标 x−1。让每个数都搬回家,扫一遍就知道谁缺席了。
- 6下面用 [3,4,-1,1,1] 一格一格演:cur 指针停在某格,该数能归位就交换,绿色 visited = 已到家。
- 7cur 落在下标0,值=3cur 停在下标0,值是 3。它在 1~5 范围内,先看该回哪个家。
- 83 的家 = 下标23 该住下标2(家=x−1)。把目标家点亮:那里现在是 -1,两格准备交换。
- 93 已到家(下标2)✓交换发生!下标0 和下标2 的值真的互换了:3 回到下标2(变绿)。cur 还在下标0,新来的是 -1。
- 10-1 不在 1~n → 停cur 处现在是 -1,负数没有家,换不动了。这格变灰,cur 准备前进到下标1。
- 11cur 移到下标1,值=4cur 移到下标1,值是 4。在范围内,看它该回哪个家。
- 124 的家 = 下标34 该住下标3。点亮目标家:那里现在是 1,两格准备交换。
- 134 已到家(下标3)✓下标1 和下标3 互换:4 回到下标3(变绿)。cur 仍在下标1,换来一个新的 1,还得继续看。
- 141 的家 = 下标0cur 没动!换来的 1 也不在家,它该住下标0。点亮下标0——这就是为什么用 while:换来的新数接着归位。
- 151 已到家(下标0)✓再次交换:下标1 和下标0 互换,1 回到下标0(变绿)。cur 处又变回 -1。
- 16-1 换不动 → cur 前进cur 处是 -1,换不动。下标1 这一轮结束,cur 前进到下标2。
- 173 已在家(下标2)✓cur 到下标2,值 3 早就在自己家了(之前归过位),无需交换,cur 前进。
- 184 已在家(下标3)✓cur 到下标3,值 4 也在自己家,跳过。只剩最后一格 1 没看。
- 19cur 到下标4,值=1cur 到最后一格下标4,又是个 1。它的家也是下标0,看看那里现在住着谁。
- 20下标0 已是 1 → 停(防死循环)下标0 已经是 1!判等条件挡住了原地死循环,这个重复的 1 留在原地,停手。归位阶段结束。
- 21[1,-1,3,4,1] 各就各位归位定型:绿色是住对了家的,灰色是没人能归位的位置。下面第二趟从左扫,找第一个「下标 i 不住 i+1」的格子。
- 22从下标0 起逐格核对归位完了,清空标记,从头开始第二趟:逐格问「下标 i 住的是 i+1 吗?」第一个不是的,就是缺口。
- 23nums[0]=1 = 0+1 ✓第二趟扫描开始。下标0 应该住 1,实际就是 1,对上了,cur 右移。
- 24nums[1]=-1 ≠ 2 → 缺 2!下标1 应该住 2,实际是 -1,对不上!第一个空家就是它 → 缺失的最小正数 = 2。
- 25把数组自己当哈希桶,既没排序也没开表,时间空间双双卡到最优。
- 28LC448(找所有消失的数)、LC442(找所有重复)、LC287(找重复数)都是这一招的变体。
- 30cur=0,值 1 想回下标0换个最小反例 [1,1]:下标0 的 1 想回下标0,可那里本就是 1,值完全相同。
- 31同值 → 停;否则无限换判等条件 nums[nums[i]−1] != nums[i] 成立时就停手。漏掉它,这两个 1 会原地无限交换——这就是死循环命门。
⚠️ 容易写错的地方
✗ 错：用 if 判断交换
✓ 对：用 while,换到不能换为止
换来的新数可能仍需归位,if 只换一次会漏
✗ 错：交换条件漏判相等
✓ 对：加 nums[nums[i]-1] != nums[i]
有重复值时,不判相等会原地反复换,死循环
完整代码（Python / C++ / Java）
Python
class Solution:
def firstMissingPositive(self, nums):
n = len(nums)
for i in range(n):
# 在范围内 且 没归位 → 交换回家
while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1: # 第一个空家
return i + 1
return n + 1C++
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n &&
nums[nums[i] - 1] != nums[i])
swap(nums[i], nums[nums[i] - 1]);
}
for (int i = 0; i < n; i++)
if (nums[i] != i + 1) return i + 1;
return n + 1;
}
};Java
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n
&& nums[nums[i] - 1] != nums[i]) {
int j = nums[i] - 1;
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}
}
for (int i = 0; i < n; i++)
if (nums[i] != i + 1) return i + 1;
return n + 1;
}
}复杂度
时间复杂度
O(n)
每次交换至少让一个数永久归位,总交换 ≤ n;两个 for 各扫一遍 → O(n)
空间复杂度
O(1)
只在原数组上交换,没开任何额外结构 → O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 缺失的第一个正数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么答案一定在 1~n+1?+
n 个位置最多放下 1~n,若全放下则缺 n+1,否则中间某个先缺。
为什么是 O(n) 不是 O(n²)?+
每次交换至少一个数永久归位,归位的数不再被换,总交换 ≤ n。
怎么防死循环?+
交换前判断目标位是否已等于该值,相等就停。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 缺失的第一个正数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。