企业网站建设具体步骤,wordpress wp-stats,建设集团有限公司,交通网站建设目录
题目链接#xff1a;41. 缺失的第一个正数 - 力扣#xff08;LeetCode#xff09;
题目描述
示例
提示#xff1a;
解法一#xff1a;标记数组法
1. 将非正数和超出范围的数替换
2. 使用数组下标标记存在的数字
3. 找到第一个未标记的位置
4. 为什么时间复杂…目录
题目链接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表示 i1 这个数字没有出现过。因为在第二步中所有出现过的数字的对应位置已经被标记为负数所以第一个正数的位置就是缺失的最小正整数。
4. 为什么时间复杂度是 O(n)
每个元素最多被处理两次第一次是在将非正数替换为 n1 时第二次是在通过下标标记数字时。因此总体的遍历次数是线性的即 O(n)。
5. 常数空间
除了输入数组 nums 本身外代码没有使用额外的数据结构比如数组、栈、队列等。空间复杂度是 O(1)因为对数组的修改都是就地进行的。 Java写法
class Solution {public int firstMissingPositive(int[] nums) {// 取得数组的长度int n nums.length;// 由于负数并不在我们的考虑范围里面所以全部放到涉及不到的地方N1for (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(vectorint nums) {// 由于在java那里的注释我已经写的很详细了这里我就随便写写了// 获取数组的长度int n nums.size();// 将小于等于零的数非正整数都设置为无关紧要的位置也就是n1for(int i 0; i n; i){if(nums[i] 0){nums[i] n 1;}}// 打标记将在[1,n1]中的数其大小对应的下标-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即第 i1 这个数字没有出现在数组中。如果找到这样的位置就说明 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(vectorint 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;}
};
运行时间 时间复杂度以及空间复杂度 总结 哇塞不愧是力扣的困难题目我现在真的越来越喜欢写困难的题目了每次写完虽然可能要花点时间但是每次写完都是一次来自大脑的洗涤思维的活跃这种逆天的感觉真的很爽加油吧兄弟们这几天我凉了从一天增加100粉丝到只有20几个了┭┮﹏┭┮
