【剑指 Offer】 03. 数组中重复的数字

[sayid760]

leetcode

[sayid760]

方法一：哈希表 空间复杂度是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]];  // 交换位置
        }
    }
};