每日一题——缺失的第一个正整数

题目描述

给定一个无重复元素的整数数组 nums，请你找出其中没有出现的最小的正整数。

进阶：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

数据范围：

• 数组元素 nums[i] 的值在 $-2^{31}\le nums[i]\le 2^{31}-1$ 之间。
• 数组长度 len(nums) 满足 $0\le len(nums)\le 5\times 10^5$。

示例

示例 1

输入：

[1, 0, 2]

输出：

3

示例 2

输入：

[-2, 3, 4, 1, 5]

输出：

2

示例 3

输入：

[4, 5, 6, 8, 9]

输出：

1

题解

本题的关键点是寻找数组中最小的缺失正整数。由于数组中没有重复的元素，我们可以利用数组下标和数值之间的关系来进行处理。具体步骤如下：

思路

1. 无效值处理：

   • 数组中值小于等于0或大于数组长度的数值不可能是我们要找的最小正整数，可以将它们替换为一个不会影响结果的数字（例如 numsSize + 1）。

2. 就地交换：

   • 数组中的每个数字应该位于它应处的位置。例如，数字 1 应该位于索引 0，数字 2 应该位于索引 1，以此类推。
   • 我们通过交换将数字放到正确的位置上。

3. 查找缺失的最小正整数：

   • 遍历数组，找到第一个没有正确放置的数字，返回它的索引对应的正整数。
   • 如果所有的数字都正确放置了，说明数组中包含了所有从 1 到 numsSize 的正整数，那么最小缺失正整数为 numsSize + 1。

代码实现

#include <stdio.h>
#include <stdlib.h>/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param nums int整型一维数组 * @param numsLen int nums数组长度* @return int整型*/
int minNumberDisappeared(int* nums, int numsLen) {// 1. 将所有不合法的数值替换为 numsLen + 1for (int i = 0; i < numsLen; i++) {if (nums[i] <= 0 || nums[i] > numsLen) {nums[i] = numsLen + 1;}}// 2. 将每个数值放到它应该在的位置上for (int i = 0; i < numsLen; i++) {int num = abs(nums[i]);  // 获取当前值的绝对值if (num <= numsLen && nums[num - 1] > 0) {nums[num - 1] = -nums[num - 1]; // 标记 num 已经出现}}// 3. 查找第一个没有标记的正整数for (int i = 0; i < numsLen; i++) {if (nums[i] > 0) {return i + 1; // 返回缺失的第一个正整数}}// 4. 如果没有缺失，返回 numsSize + 1return numsLen + 1;
}

代码解释

1. 无效值处理：

   if (nums[i] <= 0 || nums[i] > numsLen) {nums[i] = numsLen + 1;
   }
   

   • 将数组中所有小于等于0或大于 numsLen 的数值替换为 numsLen + 1，因为这些数值不可能是我们要找的最小正整数。

2. 就地交换：

   int num = abs(nums[i]);
   if (num <= numsLen && nums[num - 1] > 0) {nums[num - 1] = -nums[num - 1]; // 标记为已出现
   }
   

   • 对于每个数字 num，我们将它放到应该在的位置（即 num-1 的位置）。如果 num 在数组范围内并且当前位置的数字是正数，就将该位置标记为负数，表示该数值已出现。

3. 查找缺失的最小正整数：

   if (nums[i] > 0) {return i + 1; // 返回缺失的第一个正整数
   }
   

   • 如果遍历完数组后，遇到第一个正数，说明该索引对应的正整数是缺失的最小正整数。

4. 返回结果：

   • 如果所有 1 到 numsLen 的整数都已经出现，则返回 numsLen + 1。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们遍历数组三次：一次处理无效值，一次进行就地交换，一次查找缺失的最小正整数。
• 空间复杂度：O(1)，除了输入数组外，没有使用额外的空间，所有操作都在原数组上进行。

总结

难得的一道简单的题目。。