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