缺失的第一个正整数

[编程题]缺失的第一个正整数

热度指数：95671 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

数据范围:

$-2^{31}\le nums[i] \le 2^{31}-1$

$0\le len(nums)\le5*10^5$

示例1

输入

[1,0,2]

输出

示例2

输入

[-2,3,4,1,5]

输出

示例3

输入

[4,5,6,8,9]

输出

算法知识视频讲解

JavaScript Node

牛客814841221号

1：不重复的整形数组，对其进行sort处理

2：最小的正整数必然是1；那么我们就预先定义，假设缺失的第一个正整数就是1；然后for循环该数组，将预设的值与每一项进行匹配，若是匹配上了，那么让预设的值+1；若是最后没有匹配的值，那么我们预设的值即为第一个缺失的正整数

function minNumberDisappeared(nums) {
    // write code here
    nums.sort((a, b) => a - b);

    let preset = 1;
    for (const num of nums) {
        if (num === preset) {
            preset += 1;
        }
    }
    return preset;
}

发表于 2024-09-25 23:16:07 回复(0)

JavaScript Node

萌萌94

/**
方法三:
将有效数字(1 <= val <= N)移动到原本应该所在的位置 [0..N-1]
**/
function minNumberDisappeared( nums ) {
// write code here
let temp, N = nums.length, val;
const swap = (i, j) => {
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
for (let i = 0; i < N; i++) {
while (nums[i] > 0 && nums[i] <= N && nums[i] != i+1 && nums[i] != nums[nums[i]-1]) {
swap(i, nums[i]-1);
}
}
for (let i = 0; i < N; i++) {
if (nums[i]!=i+1) {
return i+1;
}
}
return N+1;
}

发表于 2022-05-26 18:17:57 回复(0)

JavaScript Node