【算法】数组中重复的数字

题目:在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例如下：

//输入：
[2, 3, 1, 0, 2, 5, 3]
//输出：2 或 3

自己实现（借鉴）

先排序，然后判断当前项跟后一项是否相等，相等则输出当前项

var findRepeatNumber = function(nums) {
    const arr = nums.sort()
    for(let i = 0;i < arr.length;i++){
        if(i < (arr.length-1)) {
            if(arr[i] == arr[i+1]) {
                return arr[i]
            }
        }
    }
};

效果如下：

image.png

其他思路

一、思路一

我们可以使用一个哈希表来存储数组中的每一个元素，当哈希表中已经存在数组中的元素之时，就代表重复了，直接返回该元素即可。

   /**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    const unique = new Set();
    for(const num of nums){
        if(unique.has(num)){
            return num;
        }
        unique.add(num);
    }
    return -1;
};

效果如下：

image.png

二、思路二

原地置换算法
我们尝试如此思考，因为题目很清楚的说明了数组项中的数的范围是在0~n-1之间（注意，如果没有该条件是无法使用这个算法的，这个算法也只是用时间换空间而已），也就是说比如数组的长度是2，那么数组里的所有数组项的数只能是0或1，因此我们可以猜测当数组下标等于该数组项的数的时候，则一定不会重复，如果不等于的话，那么我们把该数组项的数和等于数组下标的数做一个交换位置，在位置的交换过程中，当两者相等了，这就表明重复了。例如[1,1],两者交换位置始终都会等于1所在的数组下标，也就找到重复数字。

    var findRepeatNumber = function(nums) {
        for(let i = 0,len = nums.length;i < len;i++){
            //定义一个中间变量用于交换
            let temp;
            while(nums[i] !== i){
                if(nums[i] === nums[nums[i]]){
                    // 判断数组项对应的数是否和数组数做下标对应的数一样，如果一样则重复
                    return nums[i];
                }
                // 开始做交换
                temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }

效果如下：

image.png

总结

好像我自己想的效率高点🎉

最后编辑于：2022.08.30 15:21:59