引子

在leetcode上刷题的时候碰到一题查找重复数字的题目¹,题目内容如下

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.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

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

想到的思路都被题目的限制条件给否决了:

1. 时间复杂度小于O(n^2) (不能穷举)
2. 空间复杂度为O(1) (不能用集合Set)
3. 不能修改数组 (不能排序)

想来想去没有想到能够满足所有限制条件的方法, 最后提交了一个穷举的实现. 后来去看solution, 答案开头居然给了这么一段话:

Note

The first two approaches mentioned do not satisfy the constraints given in the prompt, but they are solutions that you might be likely to come up with during a technical interview. As an interviewer, I personally would not expect someone to come up with the cycle detection solution unless they have heard it before.

{% asset_img question.jpeg ??? %}

当然他的第三个方法满足了条件, 用的是循环检测算法(Cycle Detection) , 有点懵逼所以我决定学习下.

环检测算法(Cycle Detection)

又名: 弗洛伊德的兔子和乌龟算法(Floyd’s Tortoise and Hare)

{% asset_img question2.jpeg ??? 兔子? 乌龟? %}

一开始我也是一脸懵逼不知道这是在说什么鬼. 后来网上找了一下才明白. 这个其实是用来找链表是否有环的. 简单来说就是说

当兔子和乌龟在环形的跑道上跑步, 兔子一定会追上乌龟.

那用链表成环的情形来解释就是

用两个指针以不同的速度在链表上遍历, 如果链表有环那速度快的指正必定会上速度慢的指针.

{% asset_img floyds_tortoise_and_hare.gif Floyd’s Tortoise and Hare %}

如上图, 乌龟一次走一步兔子一次走两步,最后他们就再次相遇了.

这个算法分为两步:

1. 确认是否有环
2. 找到环的入口

确认是否有环

这个可以直接用两个速度不同的指针遍历看是否重合即可, 若遍历到末尾都未相遇则说明无环.

找到环的入口

这里我们设环的长度为C, 入口位置为I, 用两个指针h(hare, 兔子) 和 t(tortoise, 乌龟) 去遍历链表, 其中速度关系满足speed(h) = 2 * speed(t), 即快指针是慢指针速度的两倍.

{% asset_img points.png 点标注 %}

让两个指针都从头开始遍历, 记下其第一次相遇的点F, 则点F到环入口距离为X(仅表示长度), 此时:

# h走的距离
len(h) = C+F
# t走的距离
len(t) = F
# h走的距离是t走的距离的两倍
len(t)*2 = len(h) 
# 则下面的式子成立
(C + F) ==  (F + F)
# 即 环的长度与相遇点的在链表中的长度相等
C == F
# 根据一开始我们的设定
F = I-0 + F-I
C = F - I + X
# 则可以得出 F点到环入口的距离等于从起始位置到环入口的距离
X == I

得到 第一次相遇点到环入口的距离等于从起始位置到环入口的距离 这个结论之后就可以用来找环入口了.

我们让t指针指向链表开头, h指针仍指向F(这里h和t可以互换), h指针和t指针的速度都变为1,然后他们一起开始遍历, 等他们相遇的时候他们指向的节点就是环的入口.

运用环检测算法解题

对于这道题要将其看为一个链表(毕竟环检测算法是用来检测链表的).

再回顾一遍题目:

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.

把这个数组想像成一个长度为n的地址空间, 每个地址里有一个节点, 其数据为空, 只有指向下一个节点的地址(即数组下标) , 其中有两个节点指向同一个节点(数组中有两个元素的值相同), 这就形成了一个环, 而这个节点就是环的入口.

那我们需要做的就是找到那个入口.

实现代码² (Java):

class Solution {
    public int findDuplicate(int[] nums) {
        int fast =nums[0];
        int slow = nums[0];
        // 走两步
            fast=nums[fast];
            fast=nums[fast];
            // 走一步
            slow=nums[slow];
        while(fast!=slow){
            // 走两步
            fast=nums[fast];
            fast=nums[fast];
            // 走一步
            slow=nums[slow];
        }
        fast = nums[0];
        while(fast!=slow){
            // 走一步
            fast=nums[fast];
            // 走一步
            slow=nums[slow];
        }
        return fast;
    }
}

别人的文档³

Last modified on 2019-03-18