leetcode 287. Find the Duplicate Number | 287. 寻找重复数（判断链表是否有环，并找到环的起点）

朴灿烈づ我的快乐病毒、 2022-10-12 04:19 116阅读 0赞

## 题目 ##

[https://leetcode.com/problems/find-the-duplicate-number/][https_leetcode.com_problems_find-the-duplicate-number]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

题目有限制 **不能修改数组元素，必须 O(1) 空间复杂度**，所以 **不能排序，不能用 set / map**

因为本题具有 **所有数字都在 `1` 到 `n` 之间** 的特点，所以天然的（出题人故意的）可以当做一个链表来处理。

[官方题解][Link 1] 利用了与 “找到环形链表的第一个起点” 相同的思路。

### Approach 3: Floyd’s Tortoise and Hare (Cycle Detection) ###

**Intuition**

The idea is to reduce the problem to [Linked List Cycle II][]:

> Given a linked list, return the node where the cycle begins.

First of all, where does the cycle come from? Let’s use the function `f(x) = nums[x]` to construct the sequence: `x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ...`.

Each new element in the sequence is an element in nums at the index of the *previous* element.

If one starts from `x = nums[0]`, such a sequence will produce a linked list with a cycle.

> The cycle appears because `nums` contains duplicates. The duplicate node is a cycle entrance.

Here is how it works:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
Now the problem is to find the entrance of the cycle.

**Algorithm**

[Floyd’s algorithm][Floyd_s algorithm] consists of two phases and uses two pointers, usually called `tortoise` and `hare`.

**In phase 1**, `hare = nums[nums[hare]]` is twice as fast as `tortoise = nums[tortoise]`. Since the hare goes fast, it would be the first one who enters the cycle and starts to run around the cycle. At some point, the tortoise enters the cycle as well, and since it’s moving slower the hare catches the tortoise up at some *intersection* point. Now phase 1 is over, and the tortoise has lost.

> Note that the intersection point is not the cycle entrance in the general case.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]  
To compute the intersection point, let’s note that the hare has traversed twice as many nodes as the tortoise, *i.e.* 2d(tortoise)=d(hare), that means

(*F*\+*a*)=*F*\+*nC*\+*a*, where *n* is some integer.

> Hence the coordinate of the intersection point is *F*\+*a*=*nC*.

**In phase 2**, we give the tortoise a second chance by slowing down the hare, so that it now moves with the speed of tortoise: `tortoise = nums[tortoise]`, `hare = nums[hare]`. The tortoise is back at the starting position, and the hare starts from the intersection point.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]

Let’s show that this time they meet at the cycle entrance after *F* steps.

*  The tortoise started from zero, so its position after *F* steps is *F*.
 *  The hare started at the intersection point *F*\+*a*=*nC*, so its position after F steps is *nC*\+*F*, that is the same point as *F*.
 *  So the tortoise and the (slowed down) hare will meet at the entrance of the cycle.

**Implementation**

class Solution { 
        public int findDuplicate(int[] nums) { 
            int fast = nums[0];
            int slow = nums[0];
            do { 
                fast = nums[nums[fast]];
                slow = nums[slow];
            } while (fast != slow);
            slow = nums[0];
            while (fast != slow) { 
                fast = nums[fast];
                slow = nums[slow];
            }
            return fast;
        }
    }

**Result**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]

[https_leetcode.com_problems_find-the-duplicate-number]: https://leetcode.com/problems/find-the-duplicate-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/0dd81f5c50904532b0bf6be12bf6cb9f.png
[Link 1]: https://leetcode.com/problems/find-the-duplicate-number/solution/
[Linked List Cycle II]: https://leetcode.com/problems/linked-list-cycle-ii/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/f90cedeb336f49ea97b3ff8828647a63.png
[Floyd_s algorithm]: https://en.wikipedia.org/wiki/The_Tortoise_and_the_Hare
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/65d86151207f481f8d5892affac10fe3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20221005/ae5e0df978a143e0aacec950d91eace0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]: /images/20221005/65f190a27efc49e881cdaf34919e1bdf.png