41. 缺失的第一个正数
困难
给你一个未排序的整数数组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
📝 核心笔记：缺失的第一个正数 (原地哈希)
1. 核心思想 (一句话总结)
“一个萝卜一个坑”。
利用数组下标作为哈希表的 Key。我们要把数值 x 强行交换到下标 x-1 的位置上（例如：数值 1 放下标 0，数值 3 放下标 2）。
💡 直观理解：
想象你在整理杂乱的带有编号的球（1号球、5号球...）。
规则是：拿到 k号球，就把它扔到 第 k-1 个 盒子里。
最后从头检查盒子，第一个“球号不对应”的盒子，就是缺少的那个球。
2. 算法流程 (归位 -> 查岗)
- 归位 (Swapping)：遍历数组，只要当前数字
nums[i]是个“正经数”（在1到n之间），并且它没在正确的位置上，就把它交换到正确的位置去。
- 注意：交换回来的新数字可能还需要继续交换，所以用
while。
- 注意：交换回来的新数字可能还需要继续交换，所以用
- 查岗 (Checking)：再次遍历数组，看哪个下标
i里的数字不是i+1。 - 兜底：如果全都对上了，说明缺的是
n+1。
🔍 代码回忆清单 (关键点注释)
// 题目：LC 41. 缺失的第一个正数 class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { // 关键点1：While循环 (不是 if) // 只要拿到的数字符合要求，且没归位，就一直换，直到换无可换 while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) { // 防死循环：如果目标位置已经是正确的数字，就别换了 // 关键点2：交换逻辑 (把 x 放到 x-1 处) swap(nums, i, nums[i] - 1); } } // 关键点3：寻找第一个不匹配的 for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; // 找到了！缺的就是 i+1 } } return n + 1; // 既然 1~n 都在，那缺的就是 n+1 } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }⚡ 快速复习 CheckList (易错点)
- [ ]为什么用
while？
- 这是最容易错的地方。交换过来的新数字
nums[i]可能还是错的（例如把5换走了，换回来个3），3也得去它该去的地方，所以要一直换，直到当前位置无法再处理为止。
- 这是最容易错的地方。交换过来的新数字
- [ ]循环终止条件？
- 数字越界 (
<=0或>n)：没地方放，不管它。 - 目标位置已经对了 (
nums[i] == nums[target])：避免死循环（比如两个位置都是5，无限互换）。
- 数字越界 (
- [ ]时间复杂度？
- 虽然是双重循环，但每个数字最多被交换一次归位。整体是 O(N)。
🖼️ 场景模拟
数组：[3, 4, -1, 1]
- i=0 (Val=3):3 应该去下标 2。交换！->
[-1, 4, 3, 1] - i=0 (Val=-1):-1 没地方去，跳过。
- i=1 (Val=4):4 应该去下标 3。交换！->
[-1, 1, 3, 4] - i=1 (Val=1):1 应该去下标 0。交换！->
[1, -1, 3, 4] - i=1 (Val=-1):-1 跳过。
- ...
- 最后检查：下标 1 的值是 -1 (应该是 2)。返回 2。
