我将如何找到一个指针数组一个无限循环？ [英] How would I find an infinite loop in an array of pointers?

问题描述

我有一个指针数组（这是算法，所以不要去到语言细节）。大部分时间，此数组指向数组以外的位置，但它会降低到一个点，每个指针数组指向阵列中的另一个指针。最终，这些指针形成一个无限循环。

I have an array of pointers (this is algorithmic, so don't go into language specifics). Most of the time, this array points to locations outside of the array, but it degrades to a point where every pointer in the array points to another pointer in the array. Eventually, these pointers form an infinite loop.

所以在假设整个阵列由指针阵列中的另一个位置，并从头开始，如何可以找到与在时间和空间的最高效率的环的长度？我认为最好的时间效率是O（N），因为你必须遍历数组，和最好的空间效率将是O（1），虽然我不知道如何将得以实现。

So on the assumption that the entire array consists of pointers to another location in the array and you start at the beginning, how could you find the length of the loop with the highest efficiency in both time and space? I believe the best time efficiency would be O(n), since you have to loop over the array, and the best space efficiency would be O(1), though I have no idea how that would be achieved.

Index:  0  1  2  3  4  5  6
Value: *3 *2 *5 *4 *1 *1 *D

D是当时正在指向的循环开始之前的数据。在这个例子中，周期为1，2，第5和它重复无限次数，但指数0，3和4是不循环的一部分。

D is data that was being pointed to before the loop began. In this example, the cycle is 1, 2, 5 and it repeats infinitely, but indices 0, 3, and 4 are not part of the cycle.

推荐答案

这是周期检测问题的一个实例。优雅的 O（N）时间 O（1）的空间解决方案是在1960年发现的由罗伯特·W·弗洛伊德;它俗称龟和野兔的算法，因为它是由遍历与序列的两个指针，一个移动快两倍，其他的。

This is an instance of the cycle-detection problem. An elegant O(n) time O(1) space solution was discovered by Robert W. Floyd in 1960; it's commonly known as the "Tortoise and Hare" algorithm because it consists of traversing the sequence with two pointers, one moving twice as fast as the other.

我们的想法很简单：循环必须有长度的循环 K ，对于一些 K 。在每次迭代中，野兔移动两个步骤和乌龟移动一个，所以它们之间的距离是1比原来大在previous迭代。每个 K 迭代，因此，它们是 K 步骤彼此分离的倍数，一旦他们都在循环（一次乌龟到达时会发生），如果他们是 K 步骤分开，它们都指向同一元素。

The idea is simple: the cycle must have a loop with length k, for some k. At each iteration, the hare moves two steps and the tortoise moves one, so the distance between them is one greater than it was in the previous iteration. Every k iterations, therefore, they are a multiple of k steps apart from each other, and once they are both in the cycle (which will happen once the tortoise arrives), if they are a multiple of k steps apart, they both point at the same element.

如果你需要知道的是周期的长度，你的兔子和乌龟到达同一个地点等待;那么你前进的循环步骤，计算步骤，直到你回到同一地点再次。在最坏的情况下，步骤的总数将尾巴的长度加上周期长度的两倍，其中必须小于元件的数目的两倍。

If all you need to know is the length of the cycle, you wait for the hare and the tortoise to reach the same spot; then you step along the cycle, counting steps until you get back to the same spot again. In the worst case, the total number of steps will be the length of the tail plus twice the length of the cycle, which must be less than twice the number of elements.

注意：的第二段编辑为可能使理念更明显，不管这是什么意思。正式的证明是容易的，所以是一个实现，所以我提供了没有。

Note: The second paragraph was edited to possibly make the idea "more obvious", whatever that might mean. A formal proof is easy and so is an implementation, so I provided neither.

这篇关于我将如何找到一个指针数组一个无限循环？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！