LeetCode 287.寻找重复数

作者: 心谭 | 来源:发表于2020-03-10 22:06 被阅读0次

LeetCode 287. 寻找重复数 | Python
寻找重复数
LeetCode 287.寻找重复数
56. LeetCode 287. 寻找重复数
287. 寻找重复数
287. 寻找重复数
287. 寻找重复数
287. 寻找重复数
287. 寻找重复数
287. 寻找重复数

📖博客原文：《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 是为了方便在链表中表示节点：

image

那么按照规则，链表如下：

image

环的入口节点 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;
}