理解为什么弗洛伊德的龟兔赛跑算法适用于整数数组 [英] Understanding why Floyd's tortoise and hare algorithm works when applied to an array of integers

问题描述

我试图解决这个 leetcode 问题 https://leetcode.com/problems/find-the-duplicate-number/ 使用我自己的龟兔算法实现，当给定以下整数数组时会导致无限循环:

I was trying to solve this leetcode problem https://leetcode.com/problems/find-the-duplicate-number/ using my own implementation of the tortoise and hare algorithm which resulted in an infinite loop when given the following array of integers:

[3,1,3,4,2]

[3,1,3,4,2]

只有在跟踪我的算法之后，我才能看到慢速和快跑者永远不会同时接受两个重复的值.这是我的伪代码算法:

Only after tracing through my algorithm was I able to see that the slow and fast runners never take on the two duplicate values at the same time. Here is my algorithm in pseudocode:

initialize fast and slow runners to 0

while(true)

   move fast runner two indices forward
   move slow runner one index forward

   if arr[fast] == arr[slow] and fast != slow
      return arr[fast] // this is the duplicate

现在，我确信精通离散数学的人能够直观地知道这种方法不会导致正确的解决方案，而不必像我那样首先跟踪一个例子.

Now, I'm sure someone who is skilled in discrete mathematics would have been able to intuitively know that this approach would not have lead to the correct solution without first having to trace through an example like I had to do.

我可以做出哪些推论或观察，使我发现该算法行不通?我想知道如何通过一系列逻辑陈述直观地识别此逻辑中的缺陷.换句话说，为什么两个跑步者永远不会在这个例子中找到重复的解释是什么?我觉得这可能与计数有关，但我在离散方面没有很强的背景.

What inferences or observations could I have made that would have lead me to see that this algorithm was not going to work? I'd like to know how one could intuitively identity a flaw in this logic through a series of logical statements. In other words, what's the explanation for why the two runners will never find the duplicates in this example? I feel like it may have something to do with counting, but I do not have a very strong background in discrete.

澄清一下，我已经查看了正确的实现，所以我知道解决它的正确方法是什么.我只是认为这种方式与将其应用于链表的工作方式过于相似，您可以将快跑者向上移动两个节点，将慢跑者向上移动一个节点.感谢您的帮助.

And to clarify, I have looked at the correct implementation so I do know what the correct way to solve it is. I just thought that this way would have worked too similar to applying it to linked lists, where you'd move the fast runner two nodes up and the slow runner one node up. Thank you for your help.

推荐答案

Floyd 的乌龟算法在您检测链表中的循环时起作用.它依赖于这样一个事实，如果两个指针以不同的速度移动，它们之间的差距将不断增加到一个极限，之后如果存在循环，它将被重置.
在这种情况下，算法确实找到了一个循环，因为在一些迭代后，两个指针都收敛到索引 0.但是，您不想在这里检测循环；您正在尝试查找重复项.这就是为什么这会陷入无限递归:它的目的是检测循环(它正确地做到了)，但不会检测其基本实现中的重复项.

Floyd's tortoise algorithm works when you're detecting a cycle in a linked list. It relies on the fact that if both pointers are moving at a different pace, the gap between them will keep on increasing to a limit, after which it'll be reset if a cycle exists.
In this case, the algorithm does find a cycle, since both pointers converge to the index 0 after some iterations. However, you're not looking to detect a cycle here; you're trying to find a duplicate. That's why this gets stuck in infinite recursion: it is meant to detect a cycle (which it correctly does), but not detect duplicates in its basic implementation.

为了澄清，这里有一个在您的示例数组上创建的示例链接列表.

To clarify, here's a sample linked list created on your sample array.

3 -> 1 -> 3 -> 4 -> 2
'--<----<----<----<-'

如果您运行 Floyd 算法，您会发现循环将在索引 0 处被检测到，因为两个指针都会在那里收敛.它的工作原理是检查 fast 和 slow 是否指向相同位置，而不是它们是否具有相同的节点值(fast==slow 与 fast.value==slow.value 不同.

If you run Floyd's algorithm, you find that the cycle will get detected at index 0, since both pointers will converge there. It works by checking if fast and slow point to the same location and not if they have the same values of nodes (fast==slow isn't the same as fast.value==slow.value).

您正在尝试通过比较节点上的值来检查重复项，并检查节点是否指向同一位置.这实际上是缺陷，因为 Floyd 的算法会检查两个指针​​是否指向同一位置以检测循环.
您可以阅读这个简单、信息丰富的证明，以提高您对为什么指针会收敛的直觉.

You are attempting to check duplicates by comparing the value on the nodes, and checking if the nodes don't point to the same location. That is actually the flaw, since Floyd's algorithm works to check if both pointers point to the same location in order to detect a cycle.
You can read this simple, informative proof to improve your intuition as to why the pointers will converge.

这篇关于理解为什么弗洛伊德的龟兔赛跑算法适用于整数数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！