力扣最热一百题——缺失的第一个正数

题目链接：41. 缺失的第一个正数 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：标记数组法

1. 将非正数和超出范围的数替换

2. 使用数组下标标记存在的数字

3. 找到第一个未标记的位置

4. 为什么时间复杂度是 O(n)？

5. 常数空间？

Java写法：

运行时间

C++写法：

运行时间

时间复杂度以及空间复杂度

解法二：交换至正确的位置

1. 将每个数放到正确的位置上

2. 查找第一个未按顺序排列的位置

3. 如果所有数字都按顺序排列

为什么时间复杂度是 O(n)？

为什么空间复杂度是 O(1)？

困惑为什么交换的时候是while而不是if

Java解法：

运行时间

C++解法：

运行时间

时间复杂度以及空间复杂度

总结

题目链接：41. 缺失的第一个正数 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一个未排序的整数数组 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 <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

解法一：标记数组法

1. 将非正数和超出范围的数替换

for (int i = 0; i < n; ++i) {if (nums[i] <= 0) {nums[i] = n + 1;}
}

首先，代码遍历数组 nums，将其中所有非正数（即小于等于0的数）或大于 n 的数（n 是数组的长度）替换为 n + 1。因为我们只关心数组中出现的正整数，且最小的正整数应该在1到 n 的范围内，所以将这些不相关的数（非正数和大于 n 的数）统一设置为 n + 1（一个无效的值，确保不会干扰后续的逻辑）。

2. 使用数组下标标记存在的数字

for (int i = 0; i < n; ++i) {int num = Math.abs(nums[i]);if (num <= n) {nums[num - 1] = -Math.abs(nums[num - 1]);}
}

这一步的目标是通过数组中的数字来标记哪些正整数是存在的。具体逻辑是：

对每个数 num = abs(nums[i])，如果 num 在1到 n 的范围内，则将 nums[num-1] 的值设为负数。这相当于利用下标 num-1 来记录数字 num 是否出现过。
如果某个数字 num 出现了，就将位置 num-1 上的数字设为负数，表示该位置已经被标记。

3. 找到第一个未标记的位置

for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1;}
}
return n + 1;

在这一步，代码再次遍历数组，查找第一个值为正数的下标 i，表示 i+1 这个数字没有出现过。因为在第二步中，所有出现过的数字的对应位置已经被标记为负数，所以第一个正数的位置就是缺失的最小正整数。

4. 为什么时间复杂度是 O(n)？

每个元素最多被处理两次：第一次是在将非正数替换为 n+1 时，第二次是在通过下标标记数字时。因此，总体的遍历次数是线性的，即 O(n)。

5. 常数空间？

除了输入数组 nums 本身外，代码没有使用额外的数据结构（比如数组、栈、队列等）。空间复杂度是 O(1)，因为对数组的修改都是就地进行的。

Java写法：

class Solution {public int firstMissingPositive(int[] nums) {// 取得数组的长度int n = nums.length;// 由于负数并不在我们的考虑范围里面，所以全部放到涉及不到的地方N+1for (int i = 0; i < n; i++) {if (nums[i] <= 0) {nums[i] = n + 1;}}// 将每个数都打上“标记”for (int i = 0; i < n; i++) {// 由于这里的数可能在打标记的过程中被修改为负数// 所以在这里再取值的时候要取为绝对值int num = Math.abs(nums[i]);if (num <= n) {// 采用绝对值的负数，防止被打两次负数变成正数nums[num - 1] = -Math.abs(nums[num - 1]);}}// 找有没有是正数的，有的话就是他的位置for (int i = 0; i < n; i++) {if (nums[i] > 0) {return i + 1;}}// 刚才没有找到正数，那么就是数组长度加一的位置了return n + 1;}
}

运行时间

C++写法：

class Solution {
public:int firstMissingPositive(vector<int>& nums) {// 由于在java那里的注释我已经写的很详细了，这里我就随便写写了// 获取数组的长度int n = nums.size();// 将小于等于零的数（非正整数）都设置为无关紧要的位置也就是n+1for(int i = 0; i < n; i++){if(nums[i] <= 0){nums[i] = n + 1;}}// 打标记，将在[1,n+1]中的数，其大小对应的下标-1上的数置为负数for(int i = 0; i < n; i++){int num = abs(nums[i]);if(num <= n){// 为了防止nums[num - 1]已经被标记（取为负数）这里取绝对值nums[num - 1] = -abs(nums[num - 1]);}}// 找有没有正数for(int i = 0; i < n; i++){if(nums[i] > 0){// 找到了return i + 1;}}// 没找到return n + 1;}
};

运行时间

时间复杂度以及空间复杂度

解法二：交换至正确的位置

1. 将每个数放到正确的位置上

for (int i = 0; i < n; ++i) {while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {int temp = nums[nums[i] - 1];nums[nums[i] - 1] = nums[i];nums[i] = temp;}
}

这一部分的核心思想是将数组中的数字放到正确的位置上。每个数字 nums[i]，如果它在1到 n 的范围内，那么它应该出现在数组的第 nums[i] - 1 个位置。

通过 while 循环，代码不断检查 nums[i] 是否满足以下条件：
- nums[i] 是正数，并且在1到 n 的范围内。
- nums[i] 还没有被放到它应该在的位置上（即 nums[nums[i] - 1] != nums[i]）。
如果条件满足，就将 nums[i] 与它应该在的位置 nums[nums[i] - 1] 进行交换，直到每个数都被放到了正确的位置上，或者 nums[i] 已经不需要再交换了。

这个过程类似于 "桶排序"（Cyclic Sort）的思想，把数组看作一个映射，通过交换将每个数字放到对应的桶（即数组位置）中。

2. 查找第一个未按顺序排列的位置

for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) {return i + 1;}
}

在第二部分，代码再次遍历数组，寻找第一个下标 i，使得 nums[i] != i + 1，即第 i+1 这个数字没有出现在数组中。如果找到这样的位置，就说明 i + 1 是第一个缺失的最小正整数。

3. 如果所有数字都按顺序排列

return n + 1;

如果所有数字都已经按顺序排列了，那么数组中的数从 1 到 n 都出现过，这时缺失的最小正整数是 n + 1。

为什么时间复杂度是 O(n)？

每个元素最多会被交换一次，因为每次交换都把元素放到其正确的位置上。交换的次数是有限的，因此整个过程的时间复杂度是 O(n)。

为什么空间复杂度是 O(1)？

除了输入数组本身外，代码没有使用额外的数据结构，交换操作是就地进行的，因此空间复杂度为 O(1)。

困惑为什么交换的时候是while而不是if

多个元素错位的情况：
在这个问题中，目标是将每个元素放到它的正确位置，例如数字 k 应该放在数组的第 k-1 位置上。由于数组是未排序的，一个元素在经过一次交换后，它可能仍然没有被放到正确的位置。因此，代码需要反复检查并继续交换，直到这个元素被放置在正确的位置上。
确保每个元素到达正确的位置：
使用 while 的目的是让每个元素继续交换，直到它符合条件为止，即 nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] == nums[i]。如果使用 if，只能在当前条件下交换一次，但在某些情况下，交换一次后新的 nums[i] 可能仍然需要继续交换。例如，如果两个错位的元素在第一次交换后，新的元素也不在正确位置上，则需要再次交换。
示例：假设数组是 [3, 4, -1, 1]，我们希望让每个元素放在正确的位置：
- 第一个元素 3 应该放在位置 2（即下标 3 - 1 = 2）。
- 交换之后数组变为：[-1, 4, 3, 1]。注意此时 nums[0] 变为了 -1。
- 但是第一个元素现在是 -1，不符合条件（nums[0] > 0 && nums[0] <= n），所以停止处理这个位置。
- 接着处理第二个元素 4。4 应该在位置 3，交换后数组变为：[-1, 1, 3, 4]。此时 nums[1] = 1 也不在正确的位置，需要再一次交换，把 1 放到位置 0。
- 通过 while 循环，1 被正确放置在位置 0，最终得到数组 [1, -1, 3, 4]。
如果这里使用的是 if 而不是 while，那么在某些情况下，数组中的元素可能没有被交换到最终的正确位置，需要额外的遍历或逻辑来完成任务。

Java解法：

class Solution {public int firstMissingPositive(int[] nums) {// 先获取数组的长度int len = nums.length;// 进入交换数组的逻辑for(int i = 0; i < len; i++){// 由于nums[i]（本来的值）和nums[nums[i] - 1]（应该在的位置的值）// 可能在交换之后不在正确的位置上，所以需要一直交换，直到在正确的位置上while(nums[i] >= 1 && nums[i] <= len && 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 < len; i++){if(nums[i] != i + 1){return i + 1;}}// 那就是最后一位了return len + 1;}
}

运行时间

C++解法：

class Solution {
public:int firstMissingPositive(vector<int>& nums) {// 由于在java那里的注释我已经写的很详细了，这里我就随便写写了// 获取数组的长度int len = nums.size();// 交换逻辑，确保数字放到正确的位置for (int i = 0; i < len; i++) {// 不断交换，直到当前的nums[i]是有效值并且放在正确的位置上while (nums[i] >= 1 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) {// 交换时也需要防止nums[i]的值被覆盖后产生的错误int temp = nums[i];nums[i] = nums[temp - 1];nums[temp - 1] = temp;}}// 检查第一个位置不正确的元素for (int i = 0; i < len; i++) {if (nums[i] != i + 1) {return i + 1;}}// 如果所有数字都按顺序排列，则缺少的是len + 1return len + 1;}
};