【剑指 Offer】 03. 数组中重复的数字
Opened this issue · 1 comments
sayid760 commented
方法一:哈希表 空间复杂度是O(N); 需要遍历一次,时间复杂度是 O(1)
var findRepeatNumber = function(nums) {
const map=new Map()
for(let i=0; i<nums.length;i++){
if(map.has(nums[i])){
return nums[i]
}else{
map.set(nums[i], 1)
}
}
};
console.log(findRepeatNumber([2, 3, 1, 0, 2, 5, 3]))
方法二:原地哈希
不需要额外开辟空间,每次遍历时,检查当前元素是否放在了正确位置上(例如元素 i 应该放在下标为 i 的位置上)。如果放在了正确位置上,那么继续循环
var findRepeatNumber = function(nums) {
const length = nums.length;
for (let i = 0; i < length; ++i) { //0
//检测下标为i的元素是否放在了位置i上
while ((num = nums[i]) !== i) { // 比如 (num=2) !==0
if (num === nums[num]) { // 如果在其他位置找到2,则表示有重复
return num;
}
[nums[i], nums[num]] = [nums[num], nums[i]]; // 交换位置
}
}
};