1

我有一个指针数组（这是算法，所以不要进入语言细节）。大多数时候，这个数组指向数组之外的位置，但它会退化为数组中的每个指针都指向数组中的另一个指针。最终，这些指针形成了一个无限循环。

所以假设整个数组由指向数组中另一个位置的指针组成并且你从头开始，你怎么能找到在时间和空间上效率最高的循环长度？我相信最好的时间效率是 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 不是循环的一部分。

4

3 回答 3

4

这是循环检测问题的一个实例。Robert W. Floyd 在 1960 年发现了一个优雅的O(n)时空解决方案；O(1)它通常被称为“龟兔赛跑”算法，因为它包括用两个指针遍历序列，一个指针的移动速度是另一个指针的两倍。

这个想法很简单：循环必须有一个长度为的循环k，对于一些k。在每次迭代中，兔子移动两步，乌龟移动一步，因此它们之间的距离比前一次迭代大一。因此，每次k迭代，它们都是k彼此相隔的多个步骤，并且一旦它们都在循环中（一旦乌龟到达就会发生），如果它们k相隔多个步骤，它们都指向同一个元素.

如果你只需要知道周期的长度，你就等着兔子和乌龟到达同一个地方；然后你沿着循环走，数着步数，直到你再次回到同一个地方。在最坏的情况下，总步数将是尾部长度加上循环长度的两倍，循环长度必须小于元素数量的两倍。

注意：对第二段进行了编辑，以可能使这个想法“更明显”，无论这意味着什么。正式的证明很容易，实现也很容易，所以我都没有提供。

于 2013-04-18T22:15:44.487 回答
0

制作数组中元素的有向图，其中一个节点指向另一个节点，如果节点的元素指向其指向的节点的元素，并且对于每个节点。跟踪节点的入度（指向它的指针数。）在制作图表时，如果有一个入度 == 2 的节点，则该节点是无限循环的一部分。

如果第一个元素包含在无限循环中，则上述方法会失败，因此在算法开始之前，将第一个元素添加 1 indegree 以解决此问题。

于 2013-04-18T21:25:43.023 回答
0

正如您所描述的，该数组变成了一个图（更准确地说是福雷斯特），其中每个顶点的出度正好为 1。这种图的组件只能由链组成，每个链都可能以单个循环结束。也就是说，每个组件的形状要么像 O，要么像 6。（我假设没有指针为空，但这很容易处理。你最终会得到完全没有循环的 1 形组件。）

您可以通过“访问”跟踪所有这些组件，并使用“已访问”哈希或标志数组跟踪您去过的地方。

这是一个算法。

编辑 它只是为每个节点一个子节点的情况简化了一个 forrest 的 DFS，这消除了对堆栈（或递归）的需要，因为不需要回溯。

Let A[0..N-1] be the array of pointers.
Let V[0..N-1] be an array of boolean "visited" flags, initially false.
Let C[0..N-1] be an array if integer counts, initially zero.
Let S[0..N-1] be an array of "step counts" for each component trace.
longest = 0  // length of longest cycle
for i in 0..N-1, increment C[j] if A[i] points to A[j]
for each k such that C[k] = 0 
  // No "in edges", so must be the start of a 6-shaped component
  s = 0
  while V[k] is false
    V[k] = true
    S[k] = s
    s = s + 1
    k index of the array location that A[k] points to
  end
  // Loop found. Length is s - S[k]
  longest = max(longest, s - S[k])
end
// Rest of loops must be of the O variety
while there exists V[k] false
  Let k be such that V[k] is false.
  s = 0
  while V[k] is false
    V[k] = true
    s = s + 1
    k index of the array location that A[k] points to
  end
  // Found loop of length s
  longest = max(longest, s)
end

空间和执行时间都与输入数组的大小成正比 A。S如果您愿意跟踪 6 形组件两次，则 可以摆脱阵列。

另外我完全同意，如果不需要找到最大大小的循环，那么用于在链表中查找循环的古老“双指针”算法是优越的，因为它只需要恒定空间。

于 2013-04-18T21:07:29.877 回答