041.缺失的第一个整数
作者：沉默王二
发布时间：2024-08-06T16:31:14.564+0800
二哥瞎逼逼：人生最大的牢笼其实都是自己给的，以前我觉得刷 LeetCode 没多大用，也不需要，最近写 LeetCode 刷题笔记，反而得到了一些以前不曾有的快乐，尤其是对代码的一些逻辑推敲，感觉更清晰了。
题意
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
难度
困难
示例
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
### 分析 1
我们先不考虑“时间复杂度为 O(n) 并且只使用常数级别额外空间”这个限制条件。
好，先搞清楚正数是什么？
正数是大于 0 的整数，那么我们可以直接暴力来解题。
获取数组的长度 n。
从 1 开始检查每个正整数是否存在于数组中，直到找到第一个不存在的正整数。
使用双重循环，外层循环遍历正整数 i，内层循环遍历数组 nums，检查 i 是否存在于数组中。
如果当前整数 i 不存在于数组中，返回 i。
也就是说，假如输入是 [1, 2, 0]，那么我们就从 1 开始检查，1 存在于数组中，2 也存在于数组中，3 不存在于数组中，所以返回 3。
假如输入是 [3, 4, -1, 1]，还是从 1 开始检查，1 ≠ 3,1≠4，1≠-1，1=1，好，1 存在于数组中，然后开始检查 2，很显然，2 不存在于数组中，所以返回 2。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 从 1 开始检查每个正整数是否存在于数组中
for (int i = 1; i <= n + 1; i++) {
boolean found = false;
for (int j = 0; j < n; j++) {
if (nums[j] == i) {
found = true;
break;
}
}
// 如果当前整数 i 不存在于数组中，返回 i
if (!found) {
return i;
}
}
// 理论上不会执行到这里，因为我们在 for 循环中返回了结果
return n + 1;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {1, 2, 0};
int[] nums2 = {3, 4, -1, 1};
int[] nums3 = {7, 8, 9, 11, 12};
System.out.println("缺失的第一个正数: " + solution.firstMissingPositive(nums1)); // 输出 3
System.out.println("缺失的第一个正数: " + solution.firstMissingPositive(nums2)); // 输出 2
System.out.println("缺失的第一个正数: " + solution.firstMissingPositive(nums3)); // 输出 1
}
}
但是很遗憾，这种解法不符合要求，虽然很好理解。
分析 2
解决这个问题的一种有效方法是利用数组本身作为哈希表来标记出现的正数。我们可以将每个数放到它对应的索引位置上（即 1 放在 nums[0]，2 放在 nums[1] 以此类推）。最后，我们再遍历一次数组，第一个不满足条件的位置就是缺失的最小正整数。
大致的思路如下：
遍历数组，如果 nums[i] 是正数且在范围内（即 1 到 n），并且不在正确的位置上（即 nums[i] != nums[nums[i] - 1]），则交换它和它正确位置上的数。
遍历数组，第一个位置 i，使得 nums[i] != i + 1，则 i + 1 就是缺失的最小正整数。
假如输入是 [3, 4, -1, 1]，我们可以模拟整个交换过程：
交换后的结果是 [1, -1, 3, 4]，然后我们遍历数组。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
-
i = 0，nums[0] = 1，i + 1 = 1。
i = 1，nums[1] = -1，i + 1 = 2。
发现 nums[i] != i + 1，返回 2。好，来看整个题解过程。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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]) {
// 交换 nums[i] 和 nums[nums[i] - 1]
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
// 寻找第一个不满足条件的位置
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 如果所有位置都满足条件，则返回 n + 1
return n + 1;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {1, 2, 0};
int[] nums2 = {3, 4, -1, 1};
int[] nums3 = {7, 8, 9, 11, 12};
System.out.println("缺失的第一个正数: " + solution.firstMissingPositive(nums1)); // 输出 3
System.out.println("缺失的第一个正数: " + solution.firstMissingPositive(nums2)); // 输出 2
System.out.println("缺失的第一个正数: " + solution.firstMissingPositive(nums3)); // 输出 1
}
}
直接击败了 100% 的选手，效率非常高。
这个题解的关键就在于 nums[nums[i] - 1] != nums[i]，巧妙之处在于它确保了数组中的每个正整数被放置在其正确的位置上。如果一个数 x 在数组中，它应该被放在索引 x - 1 的位置上。
也就是说 2 应该出现在 2-1 的位置上，3 应该出现在 3-1 的位置上，以此类推。假如有一个不满足，那么就是缺失的最小正整数。
比如说输入是 [7, 8, 9, 11, 12]，显然 1 没有出现在 1-1 的位置上。
总结
这道题看似是一道 hard，但其实考察的内容无外乎 for 和 while 循环，当我们需要交换数组中的元素时，记得使用 temp 变量临时保存一下。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
力扣链接：https://leetcode.cn/problems/first-missing-positive/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 5900 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（ 主要是理解for 和 while 循环，以及数组的元素交换）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。