健康门户网站源码,wordpress特殊插件,没有网站如何做淘宝客,wordpress黑镜百度云盘缺失的第一个正整数 题目描述进阶#xff1a;数据范围#xff1a; 示例示例 1示例 2示例 3 题解思路代码实现代码解释复杂度分析总结 题目描述
给定一个无重复元素的整数数组 nums#xff0c;请你找出其中没有出现的最小的正整数。
进阶#xff1a;
时间复杂度#xff… 缺失的第一个正整数 题目描述进阶数据范围 示例示例 1示例 2示例 3 题解思路代码实现代码解释复杂度分析总结 题目描述
给定一个无重复元素的整数数组 nums请你找出其中没有出现的最小的正整数。
进阶
时间复杂度O(n)空间复杂度O(1)
数据范围
数组元素 nums[i] 的值在 − 2 31 ≤ n u m s [ i ] ≤ 2 31 − 1 -2^{31} \leq nums[i] \leq 2^{31} - 1 −231≤nums[i]≤231−1 之间。数组长度 len(nums) 满足 0 ≤ l e n ( n u m s ) ≤ 5 × 1 0 5 0 \leq len(nums) \leq 5 \times 10^5 0≤len(nums)≤5×105。
示例
示例 1
输入
[1, 0, 2]输出
3示例 2
输入
[-2, 3, 4, 1, 5]输出
2示例 3
输入
[4, 5, 6, 8, 9]输出
1题解
本题的关键点是寻找数组中最小的缺失正整数。由于数组中没有重复的元素我们可以利用数组下标和数值之间的关系来进行处理。具体步骤如下
思路 无效值处理 数组中值小于等于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。
复杂度分析
时间复杂度O(n)其中 n 是数组的长度。我们遍历数组三次一次处理无效值一次进行就地交换一次查找缺失的最小正整数。空间复杂度O(1)除了输入数组外没有使用额外的空间所有操作都在原数组上进行。
总结
难得的一道简单的题目。。
