深圳建站公司告诉你十个建站步骤,公司网站建设报价,一周内重大新闻事件10条,有赞小程序官网文章目录 前言1、问题2、示例3、解决方法#xff08;1#xff09;方法1 总结 前言
提示#xff1a; 1、问题 给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 看了很久… 文章目录 前言1、问题2、示例3、解决方法1方法1 总结 前言
提示 1、问题 给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 看了很久示例才看明白说了啥。 首先正整数说大于0的数字如1、2、3、4、5… 如示例1 [0,1,2]. 返回3 因为12数组中有了所以最小的为3 示例2[-1,1,3,4] 返回2。因为1和3 之间没有22就是那个丢失的第一个正整数 示例3 [7,8,9,11,12] 因为没有正整数1所以1就是那个丢失的第一个正整数
2、示例 示例 1 输入nums [1,2,0] 输出3 示例 2 输入nums [3,4,-1,1] 输出2 示例 3 输入nums [7,8,9,11,12] 输出1
3、解决方法
1方法1
let nums [3,4,-1,1]
var firstMissingPositive function(nums) {let min 1; // 1:定义一个可能返回的最小正整数nums.sort((a,b) a-b) // 2: 排序let newArray [] // 3: 定义一个接收正整数的数组// 4:第一次遍历nums.forEach((item, index) {// 4: 将数组中大于等于1 并且 小于数组长度的值 存入新数组// 如示例二新数组为[1, empty, 3]if(item 1 nums[index] nums.length){newArray[nums[index] - 1] nums[index]}});console.log(zzz, nums, newArray);// 5:第二次遍历检查下标是否喝值相对应下标1 当前下标的值for(let i0;inewArray.length;i){// 5-1:如果不等于说明当前下标1就是缺少正整数的值if(newArray[i] ! i 1){min i 1break;} else {// 5-2:如果都符合条件就如示例一中[1,2]都符合条件所以最小的值就是当前下标1 1// 下标是从0开始的当前值下标为 i 1包括最后一个值比最后一个值下标还大的就是i2了// 如示例[1,2]中2的下标为1要等于这个值就是下标1要大于这个值就是下标2// 为什么不直接使用当前item的值呢由于是用下标插入的所以item的值可以为 emptymin i 2}}console.log(mew, min); // 6:返回缺失的最小正整数
};
firstMissingPositive(nums)总结 1难度 困难 2思路遍历一次数组把大于等于1的和小于数组长度大小的值放到新数组newArray对应位置然后再遍历一次数组查当前下标是否和值对应如果不对应那这个下标1就是答案否则遍历完都没出现那么答案就是当前下标加2。 3注意点为什么要下标1和2在第五步有详细说明
