缺失的第一个整数
07/06/2021
题目描述
给你一个未排序的整数数组 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 <= 105
- -231 <= nums[i] <= 231 - 1
本人题解
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
var sup = Array.from({length: nums.length+1}).fill(false)
sup.unshift(true);
nums.forEach(i => sup[i] = true)
return sup.indexOf(false)
};第二次 2025-3-14
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
let arr = [true]
nums.forEach(num => {
if (num > 0) {
arr[num] = true
}
})
let result = arr.findIndex(item => item === undefined)
return result === -1 ? arr.length : result
};第三次 2025-8-18
function firstMissingPositive(nums: number[]): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0 && nums[i] !== i + 1 && nums[i] <= nums.length) {
putToRightPosition(nums, nums[i]);
}
}
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== i + 1) {
return i + 1;
}
}
return nums.length + 1;
};
function putToRightPosition(nums: number[], value: number) {
const nextValue = nums[value - 1] || 0;
nums[value - 1] = value
if (nextValue > 0 && nextValue <= nums.length && nextValue !== nums[nextValue - 1]) {
putToRightPosition(nums, nextValue);
}
}分析
忘了。以后再补