力扣热门100题:缺失的第正数困难
题目描述
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
提示:
解法1 去掉负数,排序
本来想去重 但是查重复杂度太高
/**
* @param {number[]} numArr
* @return {number}
*/
var firstMissingPositive = function(nums) {
let numArr=[]
nums.forEach((v)=>{
if(v>0){
numArr.push(v);
}
})
if(numArr.length==0){
return 1;
}
if(numArr.length==1&&numArr[0]>1){
return 1;
}
numArr.sort((a,b)=>parseInt(a)-parseInt(b))
let min=1;
for(let i=0;i<numArr.length;i ){
if(min!=numArr[i]){
return min;
}
if(min==numArr[i]&&numArr[i 1]!=min){
min ;
}
}
return min;
};
执行结果:
解法2 map 自增枚举
/**
* @param {number[]} numArr
* @return {number}
*/
var firstMissingPositive = function(nums) {
let map=new Map();
nums.forEach(v=>{
if(v>0){
map.set(v,1);//过滤掉负数和0 节约has方法的时间
}
});
let num=1;
while(true){
if(map.has(num)){
num ;
}else{
return num;
}
}
};
执行结果:
解法3 数组替换
将原数组有的数替换到新的数组中 使得值i 与新数组i 对应 即 a[i]=i;
/**
* @param {number[]} numArr
* @return {number}
*/
var firstMissingPositive = function(nums) {
let numArr=[]
for(let i=0;i<nums.length;i ){
numArr[nums[i]]=nums[i];
}
if(numArr[1]!=1)return 1;
for(let i=1;i<numArr.length;i ){
if(numArr[i]!=i){
return i;
}
}
return numArr.length;
};
执行结果:
解法4 标记法
/**
* @param {number[]} nums
* @return {number} 核心思想 长度为n的数组,其值为(1-n) 若其值不再这个范围内 那么1-n内必有一个缺失的正数找出这个数即可
*/
var firstMissingPositive = function(nums) {
let n=nums.length;
if(nums.indexOf(1)==-1)return 1;
// 把负数和0变成1
for(let i=0;i<n;i ){
if(nums[i]<=0||nums[i]>n){
nums[i]=1;
}
}
// 到此全为1-n内的正数
let index=0;
for(let i=0;i<n;i ){
index=Math.abs(nums[i])-1
nums[index]=-Math.abs(nums[index]);
}
//查找第一个负数
for(let i=0;i<n;i ){
if(nums[i]>0){
return i 1;
}
}
return n 1;
};
执行结果:
解法5 置换法
[3, 4, -1, 1] 为例,置换后为=>[1, -1, 3, 4]
[0, 1, 2, 2]===>[ 1, 2, 0, 1 ]
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
let n=nums.length;
for(let i=0;i<n;i ){
while(nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]){
//把对应元素交换到对应位置
let temp=nums[nums[i]-1];
nums[nums[i]-1]=nums[i];
nums[i]=temp;
}
}
for(let i=0;i<n;i ){
if(nums[i]!=i 1){
return i 1;
}
}
return n 1;
};
执行结果:
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgghiij
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13