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

心谭博客

发布于 2020-04-21 10:44:11

1K0

发布于 2020-04-21 10:44:11

文章被收录于专栏：YuanXin

题目描述：找出数组中重复的数字。在一个长度为 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]];
        }
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-02-14，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法