Leetcode 287 Floyd龟兔赛跑算法

Question:

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number 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, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

Coding:

如果没有Note里的几个要求，这题有很多解法，比如可以先排序然后找相同数字，或者利用HashSet寻找元素的时间复杂度为0(1)的特点将元素都放入Set中，直到发生碰撞。但是这些方法不是修改了原数组，就是空间复杂度不是常数，不满足题目要求。因此需要一个新的方法，也就是这一节提到的Floyd’s Tortoise and Hare，或者也叫Floyd’s判圈算法或是链表闭环判断（Cycle Detection）。

Floyd’s判圈算法通常设定两个指针，一个指针叫快指针，也可以叫兔子；另一个是慢指针，就是乌龟。兔指针每次能够走两个单位，以链表为例，就是每次可以指到当前节点的下下个节点；龟指针每次只能走一个单位，就是每次指到下一个节点。兔子和龟的起点相同，如果链表中有回环，兔子一定有再次和龟相遇的一天（追上）。如果链表中没有回环（兔指针走到头都没有和龟指针相遇），返回空；如果有回环，也即如果兔指针和龟指针相遇，返回有。

Hint: Floyd’s判圈算法通常用于判断链表中是否有回环，通常分为两步，第一步是找到是否有回环，第二步是找到回环的起始入口。通常的数组没有链表的这种结构，不存在回环的说法，但是由于题中所给的数组下标范围0 - n，存储数据的范围在1 - n之间，因此可以用当前下标所存储元素表示当前节点，下标表示上一节点，下标和存储元素的关系其实就相当于链表中上一节点指向下一节点。则数组中的回环其实就是因为有相同的存储元素，即表示两个不同的上一节点指向了相同的当前节点。而回环的起点就是那个相同的元素。
Example:

如上图所示，这是一个带环的链表（链表中的节点都隐去了）。左边是链表的起始位置，右边是链表中的环。左边无环链的长度为x1，右边环周长为C。
- 找是否有回环： 我们假设兔子和乌龟都从左边起始位置出发，当乌龟走到A时，兔子在环中B位置，这时兔子离环的起点A位置的距离是C-x2。我们让乌龟继续往前走到P点，P点离起点A的距离为C-x2，此时兔子走的路程为2*(C-x2)，也就是兔子先走到起点A，又走到P，兔子和乌龟华丽丽地相遇。
- 找到回环起点：我们已经找到了乌龟和兔子在P点相遇，P点到A点的距离为x2，链表起点到A点的距离为x1，由于x1+k*C+x2 = 2*x1，所以x1和x2同余C。那么我们设两个指针，一个指向链表开头，一个指向回环中的P点（相遇点）。两个指针每次循环更新为下一节点，它们一定会在回环起点A相遇。根据上面的分析，这个点对应的元素就是重复元素。

Java code:

public int findDuplicate(int[] nums) {
        int tortoise = 0, hare = 0;
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);
        
        int start1 = 0, start2 = tortoise;
        while (start1 != start2) {
            start1 = nums[start1];
            start2 = nums[start2];
        }
        return start1;
    }

源代码文件可参见我的Github: Solution for Find the Duplicate Number.java

Boyi Li

Leetcode 287 Floyd龟兔赛跑算法

Question:

Coding:

Reference: