当前位置：首页 > news >正文

网站开发有哪些新技术网店怎么开货源怎么找

news 2025/9/17 12:43:43

网站开发有哪些新技术,网店怎么开货源怎么找,商城首页设计,友链申请缺失的第一个正整数题目描述进阶：数据范围： 示例示例 1示例 2示例 3 题解思路代码实现代码解释复杂度分析总结题目描述给定一个无重复元素的整数数组 nums，请你找出其中没有出现的最小的正整数。进阶： 时间复杂度&#xff…

缺失的第一个正整数

- 题目描述
- - 进阶：
  - 数据范围：
- 示例
- - 示例 1
  - 示例 2
  - 示例 3
- 题解
- - 思路
  - 代码实现
  - 代码解释
  - 复杂度分析
  - 总结

题目描述

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

进阶：

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

数据范围：

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

示例

示例 1

输入：

[1, 0, 2]

输出：

示例 2

输入：

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

输出：

示例 3

输入：

[4, 5, 6, 8, 9]

输出：

题解

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

思路

无效值处理：
- 数组中值小于等于0或大于数组长度的数值不可能是我们要找的最小正整数，可以将它们替换为一个不会影响结果的数字（例如 numsSize + 1）。
就地交换：
- 数组中的每个数字应该位于它应处的位置。例如，数字 1 应该位于索引 0，数字 2 应该位于索引 1，以此类推。
- 我们通过交换将数字放到正确的位置上。
查找缺失的最小正整数：
- 遍历数组，找到第一个没有正确放置的数字，返回它的索引对应的正整数。
- 如果所有的数字都正确放置了，说明数组中包含了所有从 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;
}

代码解释

无效值处理：
```
if (nums[i] <= 0 || nums[i] > numsLen) {nums[i] = numsLen + 1;
}
```
- 将数组中所有小于等于0或大于 numsLen 的数值替换为 numsLen + 1，因为这些数值不可能是我们要找的最小正整数。
就地交换：
```
int num = abs(nums[i]);
if (num <= numsLen && nums[num - 1] > 0) {nums[num - 1] = -nums[num - 1]; // 标记为已出现
}
```
- 对于每个数字 num，我们将它放到应该在的位置（即 num-1 的位置）。如果 num 在数组范围内并且当前位置的数字是正数，就将该位置标记为负数，表示该数值已出现。
查找缺失的最小正整数：
```
if (nums[i] > 0) {return i + 1; // 返回缺失的第一个正整数
}
```
- 如果遍历完数组后，遇到第一个正数，说明该索引对应的正整数是缺失的最小正整数。
返回结果：
- 如果所有 1 到 numsLen 的整数都已经出现，则返回 numsLen + 1。