41. 缺失的第一个正数

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. 算法流程 (归位 -> 查岗)

1. 归位 (Swapping)：遍历数组，只要当前数字nums[i]是个“正经数”（在1到n之间），并且它没在正确的位置上，就把它交换到正确的位置去。

• • 注意：交换回来的新数字可能还需要继续交换，所以用while。

1. 查岗 (Checking)：再次遍历数组，看哪个下标i里的数字不是i+1。
2. 兜底：如果全都对上了，说明缺的是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也得去它该去的地方，所以要一直换，直到当前位置无法再处理为止。

• [ ]循环终止条件？

1. 1. 数字越界 (<=0或>n)：没地方放，不管它。
   2. 目标位置已经对了 (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。