我不确定您如何定义“更好”，但是也许符合条件。至少与您的解决方案以及链表问题（双关语意味深远）的解决方案不同。
如果我们走一条路
n+1 --> array[n+1] --> array[array[n+1]] --> ...
然后，当且仅当
array^k[n+1] = array^l[n+1]某某
k !=l（即，且仅当存在重复）时，此路径才包含一个循环。现在，该问题成为常见的链表问题，可以通过以下方式解决。
在第一个节点上启动两个粒子。让第一个粒子以单位速度移动，让第二个粒子以两倍单位速度移动。然后，如果有一个循环，第二个粒子将最终循环回到第一个粒子之后，最终它们将是相同的。为什么？好吧，如果您将粒子视为一个圆（一旦找到循环，它们将成为一个圆），则在每个时间单位，第二个粒子将比第一个靠近一个定向步。因此，它们最终必须碰撞。他们做到了，您发现了一个循环。要找到重复的值，只需让一个粒子静止不动，而另一个粒子再次运行循环，即可获得循环的长度。然后从头开始重新启动两个粒子，让一个向前移动循环的长度，
由于一些评论员感到愤怒，因为我没有包括如何在链表中查找循环的所有详细信息，所以现在就在这里。没有保证这不是越野车（毕竟是Matlab式的伪代码），但它至少应该解释一下这个想法。
%% STEP 1: find a point in the cycle of the linked list using a slow and fast particleslow = n+1;fast = n+1;for i=1 to n+1 slow = array[slow]; fast = array[array[fast]]; if (slow == fast) break;end%% STEP 2: find the length of the cycle by holding one particle fixedlength = 1;fast = array[fast]while fast != slow fast = array[fast]; length = length+1;end%% STEP 3: find the repeated element by maintaining constant distance between particlesslow = n+1;fast = n+1;for i=1 to length fast = array[fast];endwhile fast != slow fast = array[fast]; slow = array[slow];end%% STEP 4: return the repeated entryreturn slow;
我从这里开始是
n+1因为
array[i]介于1和n之间，所以两个粒子都不会被发送回
n+1。这样最多可以通过数组一次（虽然不是按顺序排列），并且可以跟踪两个粒子（慢和快）和一个整数（长度）。因此，空间为O（1），时间为O（n）。
