剑指offer - 数组中重复的数字 - JavaScript

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

题目描述

找出数组中重复的数字。

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

解法 1: 使用哈希表

哈希表的结构是:number-boolean,number 就是数组中的数字,boolean 代表数字是否出现过。

整体的流程是:遍历数组中的数字,检查是否出现过,如果出现过,那么返回此数字。代码实现如下:

// ac地址:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-02-14-repeat-number/

/**
 * @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;
        }
    }
};

由于使用了哈希表,所以空间复杂度是 O(N)。需要遍历一次,时间复杂度是 O(1)。

解法 2: 原地哈希(推荐)

从题目描述可以知道,所有数字都在 0 ~ n-1 的范围内。因此不需要额外开辟空间,每次遍历时,检查当前元素是否放在了正确位置上(例如元素 i 应该放在下标为 i 的位置上)。如果放在了正确位置上,那么继续循环。否则:

  • 下标为 num 的元素 === num,说明当前元素 num 是重复的,直接返回
  • 下标为 num 的元素 !== num,交换当前元素和下标为 num 的元素,将当前元素放入到正确位置上

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-02-07-half-number/

/**
 * @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]];
        }
    }
};

这里要注意的是,第二种情况交换完元素后,应该继续检测下标为 i 的元素是否放在了位置 i 上,实现上使用while内循环即可。以[1, 3, 2, 3]为例,第一次交换后,变为[3, 1, 2, 3],如果没有内循环,那么就会跳过第一个 3,继续遍历,而后面的元素又恰巧都在正确位置上,最终没有检查出重复元素。特别感谢@彻的提示。

错误代码

这段代码在 leetcode 上可以 ac,建议官方添加测试用例:[1, 3, 2, 3]

// ac地址:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-02-14-repeat-number/

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

        if (num === nums[num]) {
            return num;
        } else {
            [nums[i], nums[num]] = [nums[num], nums[i]];
        }
    }
};

更多资料

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×