寻找重复数 - 快慢指针解法原理

本文最后更新于:2020年11月22日 晚上

是龟兔赛跑。

前言

突然刷到了一个视频If Programming Was An Anime

里面的快慢指针很有趣,刚好有兴趣,那就写一下吧。

正文

要用快慢指针解决寻找重复数的话要证明两个部分。一个部分是这个题一定会构造出一个环,一个是快慢指针用来寻找环的入口的证明。

证明根据题意一定会构造出一个环

我们可以先想象出一个由 1 到 n+1 的数列,将它们打乱放置在下标从 0 到 n 的数组 nums[]中。假设有个函数可以根据值返回它在数组中的下标 getIndex()

我们可以知道 nums[0]的入度为 0,而值为 n+1 的 nums[getIndex(n+1)]的出度为 0,数组中的其他的入度和出度都是 1。这个时候可能会生成很多的环,但是如果将 nums[0]作为入口的话,是不可能出现环的,因为 nums[0]的入度为 0,没有指向 nums[0]的值。

现在我们将由 nums[0]为起点的这个链表找到,假设值为 n+1 的数字在这个链表中,那么把它改为 1~n 中的任意一个数,记为 p,此时我们可以知道 nums[p]的入度为 2,因为有两个指向它的指针。同时原本值为 n+1 的这个数的有了出边,指向了 nums[p]

当值为 p 的 nums[getIndex§]在以 nums[0]开头的这个链表中时,我们可以很轻易的想象出来这个这条链表形成了一个环,包括了 nums[p]到 nums[x]的这一系列节点。

那么当这个值为 p 的 nums[getIndex§]不在以 nums[0]开头的这个链表中时,它在另外的一个链表中。举个例子 [1,4,3,2,5]。此时 nums[2] 和 nums[3]形成了一个环,我们将 nums[4]的值改为 3, 即 nums == [1,4,3,2,3] 我们可以看到从 nums[0]开始的链表最后还是会进入到一个环中。

那么值为 n+1 的数字不在这个链表中呢?其实这并不可能,因为它没有出边,那么它不可能在一个环中,因为所有的节点出度都是 1,所以必然不存在一个环中的节点既能指向环中的节点,又能指向环外的节点。因此这个 nums[getIndex(n+1)]必然在以 nums[0]开头的链表中。

证明使用快慢指针来寻找环的入口

通过上面的证明我们知道了根据题意我们会构造出一个环,而环的入口就是那个重复的数。

那么我们应该怎么找到这个重复的数呢?简单地说定义两个指针,一个慢指针 (slow) 每次走一步,一个快指针 (fast) 每次走两步。当快慢指针指向的数组下标相等时就将快指针放回数组的头部,然后继续走,当快慢指针指向的数组下标相等时,这个值就是要找的环的入口。

那么问题是,怎么证明呢?

如下图,令 A 点为起始点,B 点为环的入口,C 点为慢指针首次到达 B 点时快指针的位置,D 点为快慢指针首次在环中相遇的地点。记 AB 的距离为 a,BC 的距离为 b, 环的周长为 R。

定义

我们让慢指针的速度为 v1v_{1} ,快指针的速度为 v2v_{2} 。令v2=2v1v_{2} = 2 * v_{1},即慢指针每次走一步,快指针每次走两步

快慢指针

那么当慢指针到达 B 点时,快指针已经走了 S1=a+b+nRS_{1} = a+b+n*R 其中 n 为快指针在环里已经绕过的圈数。又知道快指针的速度为慢指针的两倍,所以快指针走过的路程 S1=2aS_{1} = 2 * a 即慢指针走过的路程的两倍。我们将其整理可以得到 a=nR+ba = n * R + b

慢指针到 B 点
因为快指针每次走两步,慢指针每次走一步。所以快指针每次比慢指针多走一步。在慢指针到达 B 点时,快指针和慢指针的距离是 S2=Scb=RbS_{2} = S_{cb} = R - b 。也就是说从现在开始,到两者首次相遇在 D 点,慢指针要走S3S_{3} = S2=RbS_{2} = R-b 这么多步。那么这个时候因为 v2=2v1v_{2} = 2 * v_{1} 所以快指针走的距离为 S4=2S2=2(Rb)S_{4} = 2 * S_{2} = 2 * (R - b)

因为在慢指针刚到达 B 点时,快指针在 C 点,所以当两者在 D 点相遇时,快指针相对于 B 点的距离为 S5=S4+b=2RbS_{5} = S_{4} + b = 2 * R - b 。因为 R 为环的周长所以可以约去,因此此时快指针相对于 B 点的距离为 b=b|-b| = b 即 D 点与 C 点刚好形成一个对称关系。

快慢指针 D 点相遇
此时我们将快指针移回原点 A,并且让它的速度为 v3=v1v_{3} = v_{1} 如果让快指针从 A 点走到 B 点那么可以知道此时快慢指针走过的路程相同 S6=a=nR+bS_{6} = a = n * R + b 。因为 R 为环的周长所以对于在环里的慢指针而言可以约去,此时我们会发现当快指针到达 B 点的时候,慢指针也到达了 B 点,此时的 B 点正好是环的入口。
快指针移回原点

参考

【链表】【证明】快慢指针判断链表有环、寻找环入口、计算环大小的原理