LeetCode 287.寻找重复数 - JavaScript

题目描述:给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

说明:

  • 不能更改原数组(假设数组是只读的)。
  • 只能使用额外的 $O(1)$ 的空间。
  • 时间复杂度小于 $O(n^2)$ 。
  • 数组中只有一个重复的数字,但它可能不止重复出现一次。

解法 1: 原地哈希

这种思路和《LeetCode 442.数组中重复的数据》一样,用数组元素的符号代表当前元素是否出现过:

  • nums[i] < 0: 数字 i 出现过
  • nums[i] > 0: 数字 i 没出现过

代码实现:

// ac地址:https://leetcode-cn.com/problems/find-the-duplicate-number/
// 原文地址:https://xxoo521.com/2020-03-03-find-the-duplicate-number/
/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    const length = nums.length;

    for (let i = 0; i < length; ++i) {
        const val = Math.abs(nums[i]);
        if (nums[val] < 0) {
            return val;
        } else {
            nums[val] *= -1;
        }
    }
};

注意:这种解法不符合“说明”中的第一条,不能更改原数组。

解法 2: Floyd 算法(符合题意)

Floyd 算法才是符合“说明”中的所有要求的正确解法。Floyd 算法是为了解决链表中是否存在环,以及环的入口的问题,有两道相关的题目,可以通过它们来掌握 Floyd 的应用:

那么,现在的问题关键是怎么将数组转换为链表判环的问题?

由于数组长度是 n + 1,里面元素的范围是【1,n】。所以,对于值为 v 的元素,可以将它看作链表中的一个节点,定义它的 next 指针指向 nums[v]。若是存在重复数字,则这条链表中一定存在环,且唯一重复的数字是环的入口。

为了方便说明,我们以下面的数组为例。index 是下标,val 是值,name 是为了方便在链表中表示节点:

那么按照规则,链表如下:

环的入口节点 C 对应着 val 为 3,就是我们要找的重复数字。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/find-the-duplicate-number/
// 原文地址:https://xxoo521.com/2020-03-03-find-the-duplicate-number/
/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let intersect = getIntersect(nums);
    let ptr1 = nums[0];
    let ptr2 = intersect;
    while (ptr2 !== ptr1) {
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }

    return ptr2;
};

/**
 * @param {number[]} nums
 * @param {number}
 */
function getIntersect(nums) {
    let fast = nums[0];
    let slow = nums[0];

    do {
        slow = nums[slow];
        fast = nums[fast];
        fast = nums[fast];
    } while (fast !== slow);

    return fast;
}

更多资料

若有纰漏,欢迎指正。若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

评论

Your browser is out-of-date!

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

×