??博客原文 ：《LeetCode 287.尋找重復(fù)數(shù) - JavaScript》

題目描述：給定一個(gè)包含 n + 1 個(gè)整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個(gè)重復(fù)的整數(shù)。假設(shè)只有一個(gè)重復(fù)的整數(shù)，找出這個(gè)重復(fù)的數(shù)。

說明：

• 不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）。
• 只能使用額外的 的空間。
• 時(shí)間復(fù)雜度小于 。
• 數(shù)組中只有一個(gè)重復(fù)的數(shù)字，但它可能不止重復(fù)出現(xiàn)一次。

解法 1: 原地哈希

這種思路和《LeetCode 442.數(shù)組中重復(fù)的數(shù)據(jù)》一樣，用數(shù)組元素的符號(hào)代表當(dāng)前元素是否出現(xiàn)過：

• 若nums[i] < 0: 數(shù)字 i 出現(xiàn)過
• 若nums[i] > 0: 數(shù)字 i 沒出現(xiàn)過

代碼實(shí)現(xiàn)：

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

注意：這種解法不符合“說明”中的第一條，不能更改原數(shù)組。

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

Floyd 算法才是符合“說明”中的所有要求的正確解法。Floyd 算法是為了解決鏈表中是否存在環(huán)，以及環(huán)的入口的問題，有兩道相關(guān)的題目，可以通過它們來掌握 Floyd 的應(yīng)用：

• LeetCode 141.環(huán)形鏈表
• LeetCode 142.環(huán)形鏈表

那么，現(xiàn)在的問題關(guān)鍵是怎么將數(shù)組轉(zhuǎn)換為鏈表判環(huán)的問題？

由于數(shù)組長度是 n + 1，里面元素的范圍是【1，n】。所以，對(duì)于值為 v 的元素，可以將它看作鏈表中的一個(gè)節(jié)點(diǎn)，定義它的 next 指針指向 nums[v]。若是存在重復(fù)數(shù)字，則這條鏈表中一定存在環(huán)，且唯一重復(fù)的數(shù)字是環(huán)的入口。

為了方便說明，我們以下面的數(shù)組為例。index 是下標(biāo)，val 是值，name 是為了方便在鏈表中表示節(jié)點(diǎn)：

image

那么按照規(guī)則，鏈表如下：

image

環(huán)的入口節(jié)點(diǎn) C 對(duì)應(yīng)著 val 為 3，就是我們要找的重復(fù)數(shù)字。

代碼實(shí)現(xiàn)如下：

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

更多資料

若有紕漏，歡迎指正。若對(duì)您有幫助，請(qǐng)給個(gè)「關(guān)注+點(diǎn)贊」，您的支持是我更新的動(dòng)力 ??

• ??Blog：劍指 Offer + Leetcode 題解
• ??Github ：https://github.com/dongyuanxin/blog
• ?? 公眾號(hào)：心譚博客