力扣287——尋找重複數

這道題主要就是找規律，基於之前142題環形鏈表II的規律，就能解決了。

原題

給定一個包含 n + 1 個整數的數組 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重複的整數。假設只有一個重複的整數，找出這個重複的數。

示例 1:

<code>輸入: [1,3,4,2,2]
輸出: 2/<code>

示例 2:

<code>輸入: [3,1,3,4,2]
輸出: 3/<code>

說明：

• 不能更改原數組（假設數組是隻讀的）。
• 只能使用額外的 O(1) 的空間。
• 時間複雜度小於 O(n2) 。
• 數組中只有一個重複的數字，但它可能不止重複出現一次。

原題url：https://leetcode-cn.com/problems/find-the-duplicate-number/

解題

普通思路

針對說明裡的前兩條，其實就分別對應瞭解題的兩種思路：

1. 先原地排序，再遍歷尋找。
2. 使用集合記錄已經出現過的數字。

當然了，既然已經在說明裡被禁止了， 那麼就應該想想別的思路了。

我還想到了利用 bitMap 的思路，相當於用一個數字的二進制，各個位上是否為1來表示該數字是否出現過。但考慮到 java 裡 int 的最大值是 (2^31 - 1)，long 的最大值也不過是(2^63 - 1)，那都是要求 n 不能大於100的。因此，這種思路也是暫時不可取的。

抽象為環形鏈表II

如果將數組的下標和值抽象成鏈表的話，出現重複數字也就意味著出現鏈表中有環，那麼這道題就是之前做到的力扣142——環形鏈表II一模一樣了。

我們舉例說明一下，假設數組是[1, 5, 7, 3, 2, 4, 6, 7]，那麼將其轉化成的鏈表就是：`0 -> 1 -> 5 -> 7 -> 3 -> 2 -> 4 -> 6 -> 7 ....`無限循環。

那我們就可以藉助快慢指針：

1. 快指針一次走兩步，慢指針一次走一步，直到他們相遇；
2. 快指針再次從起點出發，但此時兩個指針都是一次走一步；
3. 當他們再次相遇後，相遇點就是重複的整數。

接下來讓我們看看代碼：

<code>class Solution {
    public int findDuplicate(int[] nums) {
        // 參考環形鏈表II，利用快慢指針
        // 快指針一次走兩步，慢指針一次走一步，當他們相遇後
        // 快指針再次從起點出發，但此時兩個指針都是一次走一步
        // 當他們再次相遇後，相遇點就是重複的整數

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

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

        return fast;
    }
}/<code>

提交OK，時間複雜度為：O(n)，空間複雜度是：O(1)。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題目主要還是在於尋找其中的規律，轉化為環形鏈表來思考。

有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。

https://death00.github.io/

公眾號：健程之道