leetcode筆記：Find the Duplicate Number

leetcode筆記：Find the Duplicate Number

一. 題目描述

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate element must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).
You must use only constant extra space.
Your runtime complexity should be less than O(n^2).
There is only one duplicate number in the array, but it could be repeated more than once.

二. 題目分析

題目的大意是，給定一個包含n + 1個整數的數組，其中每一個整數的大小均在[1, n]之間，證明其中至少有一個重復元素存在。同時假設數組中只有一個數字出現重復，找出這個重復的數字。

注意事項：

題目的限定要求非常多，一開始並不能想到最優方法，這裡給出一種新穎的方法：映射找環法，其實這種方法來源於鏈表找環。時間復雜度為O(n)，空間復雜度O(1)。

首先，假設一個數組中沒有重復，則可以將數組的下標和其對應元素(1 ~ n)一一的映射起來。舉個例子，對於數組[4, 1, 3, 2]，則映射關系為0 -> 4, 1 -> 1, 2 -> 3，3 -> 2。

這個映射關系可表示一個函數f(n)，其中n是下標，f(n)是映射到的數。如果我們從下標為0出發，根據這個函數計算出一個值，以這個值為新的下標，再用這個函數計算，以此類推，可以產生一個類似於鏈表的序列。

此時，如果數組本身有重復的元素，就會出現多對一的映射，比如數組[2, 1, 3, 1]，則映射關系為：0 -> 2, {1, 3} -> 1, 2 -> 3。熟悉鏈表的朋友知道，這一序列中出現了環路！與鏈表一致，如果遍歷這個映射關系：0 -> 2 -> 3 -> 1 -> 1 -> 1 -> ...，其中，環的起點就是題目所要求的重復的數。

所以該題實際上可轉化為求環路起點，實現方法與Linked List Cycle II一題類似。同樣，使用快慢（fast，slow）兩個下標，從0開始，快下標每次循環時映射兩次，即：fast = num[num[fast]]，而慢下標每次循環映射一次，即：slow = num[slow]，直到fast == slow，這個階段相當於鏈表找環時，快指針與慢指針相遇，這一結論證明鏈表有環，對應到本題中，則能證明數組內有重復元素！

第二步，是找出這個重復元素，也就是找出環的入口，這時需要另一個變量finder從下標0出發，和fast的操作一致，每次循環映射兩次：fast = num[num[fast]]，同時，slow保持一次映射。當這兩個下標相遇時，slow就是環的起點，也就是重復的數。

三. 示例代碼

class Solution {
public:
    int findDuplicate(vector& nums) {
        int slow = 0;
        int fast = 0;
        int finder = 0;

        while (true)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];

            if (slow == fast)
                break;
        }

        while (true)
        {
            slow = nums[slow];
            finder = nums[finder];
            if (slow == finder)
                return slow;
        }
    }
};

四. 小結

該題的思路相當新穎，不容易想到，此外，還有使用二分法來解決的方案，但不是最優方案。