本题在线练习：LeetCode 41. 缺失的第一个正数 - 在线练习（免费 · 无需登录 · AI 辅助）(https://onefly.top/zero2Leetcode/playground.html?id=41)
配套刷题网站 Zero2Leetcode —— 内置本地 OJ + AI 教练，零门槛开始刷 Hot 100。
题目概述
给定一个未排序整数数组 nums，找出其中缺失的最小正整数。
要求：时间 O(n)，额外空间 O(1)。
这题的难点在于：既要线性时间，又不能用额外哈希集合。正确思路是“原地哈希”：把值 x 放回它应该在的位置 x-1。
核心思路：答案只可能在 [1, n+1]
数组长度为 n，如果 1..n 都存在，那么最小缺失正数就是 n+1。
所以只需要关心区间 [1, n] 内的数，其他（负数、0、>n）都可以忽略。
目标：让数组满足尽可能多的“值归位”：
如果数组里有数
x（1<=x<=n），就尝试把它放到下标x-1的位置上。
归位完成后，再从头扫一遍，找到第一个 nums[i] != i+1 的位置，答案就是 i+1。
代码实现（原地交换归位）
class Solution:def firstMissingPositive(self, nums: list[int]) -> int:n = len(nums)i = 0while i < n:x = nums[i]# x 应该放在 idx = x-1if 1 <= x <= n and nums[x - 1] != x:nums[i], nums[x - 1] = nums[x - 1], nums[i]else:i += 1for i in range(n):if nums[i] != i + 1:return i + 1return n + 1
逐行拆解：为什么要用 while 而不是 for
因为交换后 nums[i] 变成了一个新值，可能仍然需要继续归位。
用 while：
- 如果发生交换，不增加
i，继续处理当前位置 - 如果不需要交换，才
i += 1
这样能确保每个值最多被交换到位一次，整体仍是 O(n)。
手动模拟：nums = [3,4,-1,1]
n=4，只关心 1..4。
- i=0，x=3 应放到 idx=2：交换 ->
[-1,4,3,1] - i=0，x=-1 无视，i=1
- i=1，x=4 应放到 idx=3：交换 ->
[-1,1,3,4] - i=1，x=1 应放到 idx=0：交换 ->
[1,-1,3,4] - i=1，x=-1 无视，继续
归位后从头扫：
- i=0 是 1 对
- i=1 不是 2，答案 = 2
复杂度分析
- 时间：
O(n)（每个元素交换次数有限） - 空间：
O(1)
总结
缺失的第一个正数的关键思路是“原地哈希”：
- 只关心
[1, n] - 把值
x放到下标x-1 - 再线性扫描找第一个不匹配的位置
把“数组当哈希表”这个技巧吃透，后面很多原地题（找缺失数、找重复数的变种）都会更有把握。