算法题：缺失的第一个正整数
今天，我们来聊聊一道经典的算法题：缺失的第一个正整数。这题乍一看似乎不复杂，简单遍历一下数组就能解决，但在面试时它其实是个挺考验思维深度的题目，尤其是对于优化的要求。
你也许会觉得：这题不就是找到缺失的正数吗？但如果告诉你，要求时间复杂度是 O(n)，空间复杂度是 O(1)，你可能就得好好动动脑筋了。
给定一个无序的整数数组 nums，你需要找到其中缺失的第一个正整数。这里面有两个关键点：
时间复杂度必须是 O(n)。 空间复杂度必须是 O(1)。
简单来说，就是不能用额外的空间存储什么数据，也不能通过二次遍历来进行比较。你想过没有，咋样才能同时满足这两个条件？
刚开始我也想用暴力方法来解：将所有正整数存到一个集合中，然后逐个检查哪一个数字缺失。然而，这种方法的空间复杂度是 O(n)，显然不符合要求。那么有没有更聪明的方法呢？
经过一番思考，我意识到其实数组本身就可以作为我们的一种“存储工具”。我们可以通过数组的索引来标记哪些数字已经出现过。比如说，数字 1 应该在 nums[0] 位置，数字 2 应该在 nums[1] 位置，依此类推。只要我们能保证每个数字都尽量放到它该在的位置，就能很轻松地找到缺失的那个数字。
具体来说，我们的做法是：
先对数组进行一次遍历，把每个数字放到它应该在的位置上。比如，数字
x应该放在nums[x-1]这个位置。然后，我们再遍历一次数组，查找第一个位置不对的数字，返回该位置对应的值，就是缺失的第一个正整数。
代码实现
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 第一遍遍历：将正整数放到它应该在的位置
for (int i = 0; i < n; i++) {
// 当前数字如果在有效范围内（1到n），并且它不在正确的位置，进行交换
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// 交换 nums[i] 和 nums[nums[i] - 1] 的位置
int temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
}
}
// 第二遍遍历：找出第一个位置不正确的数字
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 如果所有位置都正确，说明缺失的正整数是 n+1
return n + 1;
}}交换操作：我们首先检查每个数字是否在
1到n的范围内。如果是，并且它不在正确的位置，就交换它与它应该在的位置的元素。这样，我们保证了每个数字尽可能放到了它应该在的位置。第二次遍历：完成第一步后，我们再遍历一遍数组，检查哪个位置上的数字不对。如果
nums[i] != i + 1，那就说明i + 1这个数字缺失了。时间复杂度：由于每个元素最多会被交换一次，所以整个过程的时间复杂度是 O(n)。
空间复杂度：我们没有使用额外的空间来存储数据，所以空间复杂度是 O(1)，符合题目要求。
举个例子
假设给定数组是 [3, 4, -1, 1]，我们通过代码的交换操作会得到如下结果：
初始数组：[3, 4, -1, 1]
第一次交换：[1, 4, -1, 3]
这里，数字 1 被交换到nums[0]位置，数字 3 被交换到nums[2]位置，剩下的负数和不符合范围的数被忽略。第二次遍历，我们发现位置 1 和位置 2 的数字不对，因此缺失的第一个正整数是
2。
有些同学可能会想：“如果用哈希表不是可以直接记录每个出现的正整数吗？”确实，哈希表的查找时间复杂度是 O(1)，而且非常直观，但它的空间复杂度是 O(n)，这和题目的要求冲突了。
所以我们不得不利用数组本身来做标记，才能满足空间复杂度 O(1) 的要求。
好了，今天就聊到这里，大家有问题可以留言讨论哦~
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
