原地哈希
解题思路
原地哈希就相当于，让每个数字 n 都回到下标为 n-1 的家里；
而那些没有回到家里的就成了孤魂野鬼流浪在外，他们要么是根本就没有自己的家（数字 <=0 或者 >nums.length），要么是自己的家被别人占领了（出现了重复）；
这些流浪汉被临时安置在下标为 i 的空房子里，之所以有空房子是因为房子 i 的主人 i+1 失踪了；
因此通过原地构建哈希让各个数字回家，就可以找到原始数组中重复的数字还有消失的数字（n 一定在
[1, nums.length]这个区间里面）：
复杂度
-
时间复杂度：
O(n) -
空间复杂度：
O(1)
实现代码
var firstMissingPositive = function (nums) {
let len = nums.length;
let i = 0;
while (i < len) {
let num = nums[i];
if (num > 0 && nums[num - 1] !== num && num <= len) {
swap(nums, i, num - 1);
} else {
i++;
}
}
for (let i = 0; i < len; i++) {
if (nums[i] !== (i + 1)) {
return i + 1;
}
}
return len + 1;
};
const swap = (nums, i, j) => {
[nums[i], nums[j]] = [nums[j], nums[i]]
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
Redis👉 缓存响应体 (案例)
上一篇
评论
