建网站用哪个好,怀化举报网站,免费足网站,做淘客网站需要营业执照吗题目#xff1a;
解题一#xff1a;
如果不考虑时间复杂度和空间复杂度的话#xff0c;我们最先想到的办法是先将该数组进行排序和去重#xff0c;将最初的res结果值设置为1#xff1b;将然后进行遍历#xff0c;如果第一项不为1#xff0c;则返回1#xff0c;否则根…题目
解题一
如果不考虑时间复杂度和空间复杂度的话我们最先想到的办法是先将该数组进行排序和去重将最初的res结果值设置为1将然后进行遍历如果第一项不为1则返回1否则根据遍历res遍历结束后发现每一项都符合要求则返回res的最终值。代码如下
代码一
/*** param {number[]} nums* return {number}*/
var firstMissingPositive function(nums) {nums Array.from(new Set(nums));nums.sort((a,b)a-b);let res 1;for(let i 0; i nums.length;i){if(nums[i] 0){if(nums[i] ! res){return res;}res;}}return res;
};sort函数的时间复杂度为O(n log n)空间复杂度为O(n) new Set操作的时间复杂度是O(n)空间复杂度也是O(n) 以上代码并没有满足题目要求的时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
解题二
我们这次使用了一个SetnumSet来存储数组中出现过的正数。首先我们遍历原数组nums将每个在1到n范围内的正数添加到Set中。然后我们再次遍历从1到n的每个数字检查它是否在Set中出现过。如果找到一个没有出现过的数字我们就返回它作为缺失的第一个正整数。如果所有1到n的数字都出现过我们则返回n1。
代码二
/*** param {number[]} nums* return {number}*/
var firstMissingPositive function(nums) {let numSet new Set();let n nums.length;for(let i 0; i n;i){if(nums[i] 0 nums[i] n){numSet.add(nums[i]);}}for(let i 1; i n;i){if(!numSet.has(i)){return i;}}return n 1;
};但是我们使用了一个额外的Set来存储出现过的数字所以这里的空间复杂度为O(n)时间复杂度是O(n)因为我们只遍历了数组两次并且Set的查找和插入操作都是O(1)的。
解题三
将所有负数、0 都变为 N 1我们只需要考虑1-n的数字 遍历每个数如果该数 |x| 属于[1,N]把在 x-1 的位置的数加上一个负号 遍历完之后如果全部数都是负数——答案就是 1N否则就是第一个正数的位置1
代码三
/*** param {number[]} nums* return {number}*/
var firstMissingPositive function(nums) {let n nums.length;for(let i 0; i n;i){if(nums[i] 0) nums[i] n 1;}for(let i 0; i n;i){let x Math.abs(nums[i]);if(x 1 x n){nums[x - 1] nums[x - 1] 0 ? nums[x - 1] : -nums[x - 1];}}for(let i 0; i n;i){if(nums[i] 0) return i1;}return n 1;
};此时就满足时间复杂度为o(n),空间复杂度为常数的代码了。此思路借鉴于力扣博主okkjoo具体地址点击此处跳转。 当博主问朋友解决方案的时候他二话不说的告诉我“用桶排啊”于是、、、、这篇文章到这里没有结束明天博主会尽快将桶排的方法补充上去也欢迎小伙伴们在评论区留下你们的答案哦~~~~~
