Nob*_*ift 1 arrays algorithm big-o pointers infinite-loop
我有一个指针数组（这是算法，所以不要讨论语言细节）。大多数时候，该数组指向数组外部的位置，但它会退化为数组中的每个指针都指向数组中的另一个指针。最终，这些指针形成无限循环。
因此，假设整个数组由指向数组中另一个位置的指针组成，并且从头开始，如何找到在时间和空间上效率最高的循环长度？我相信最好的时间效率是 O(n)，因为你必须循环数组，最好的空间效率是 O(1)，尽管我不知道如何实现。
Index: 0 1 2 3 4 5 6
Value: *3 *2 *5 *4 *1 *1 *D
D 是循环开始之前指向的数据。在此示例中，循环为 1、2、5，并且无限重复，但索引 0、3 和 4 不是循环的一部分。
这是循环检测问题的一个例子。1960 年，罗伯特·W·弗洛伊德 (Robert W. Floyd) 发现了一种优雅的O(n)时空解决方案；O(1)它通常被称为“龟兔赛跑”算法，因为它使用两个指针遍历序列，其中一个指针的移动速度是另一个指针的两倍。
这个想法很简单：循环必须有一个长度为 的循环k，对于某些k。在每次迭代中，兔子移动两步，乌龟移动一步，因此它们之间的距离比上一次迭代中的距离大一。因此，每次迭代，它们彼此相距k多个步骤，一旦它们都进入循环（乌龟到达后就会发生），如果它们相距多个步骤，则它们都指向同一个元素。kk
如果你只需要知道周期的长度，你就等待兔子和乌龟到达同一个地方；然后你沿着循环走下去，数着步数，直到再次回到同一个地方。在最坏的情况下，总步数将是尾部长度加上循环长度的两倍，这必须小于元素数量的两倍。
注意：第二段经过编辑，可能使这个想法“更加明显”，无论这意味着什么。形式证明很容易，实现也很容易，所以我两者都没有提供。