剑指offer 03数组中重复数

た入场券 2023-01-12 10:26 115阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]

## JS ##

/** * @param {number[]} nums * @return {number} */
    var findRepeatNumber = function(nums) { 
        const len = nums.length;
        for(let i =0;i<len-1;i++){ 
            for(let j=i+1;j<len-1;j++){ 
                if(nums[i]===nums[j]){ 
                    return nums[i] ;
                }
            }
        }
        return nums[len-1];
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]笨比解法没什么好说的

--------------------

## JS优化（使用set） ##

/** * @param {number[]} nums * @return {number} */
    var findRepeatNumber = function(nums) { 
        let s=new Set();
        for(var i in nums){ 
            var curLenth=s.size;
            s.add(nums[i]);
            if(s.size==curLenth)
            return nums[i];
        }
    };

用时116ms ，46.4内存。set方法去重再根据长度是否增加判断是否重复，很妙。

--------------------

## JS优化（使用map） ##

/** * @param {number[]} nums * @return {number} */
    var findRepeatNumber = function(nums) { 
        const map = { };
        for (const num of nums) { 
            if (!map[num]) { 
                map[num] = true;
            } else { 
                return num;
            }
        }
    };

map、js对象、哈希表个人理解差不多一个意思，也很简单的解法。  
用时104ms

--------------------

## JS优化（使用原地哈希） ##

// /**
    // * @param {number[]} nums
    // * @return {number}
    // */
    var findRepeatNumber = function(nums) { 
        const length = nums.length;
        for (let i = 0; i < length; ++i) { 
            //检测下标为i的元素是否放在了位置i上
            while ((num = nums[i]) !== i) { 
                if (num === nums[num]) { 
                    return num;
                }
                [nums[i], nums[num]] = [nums[num], nums[i]];
            }
        }
    };

用时100ms  
寻求更快的解法，从题解里找到了原地哈希，画图理解了一下，和本题的条件范围相符才可用。时间复杂度也是On。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221119/050c764797a34abfb539cc5babb0bfcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/5824d432f21d40b894a146c34ba8def0.png