java - 在 Java 的数组上下文中，指针加倍意味着什么？

Question

Find a duplicate. Given an array of N+1 elements in which each element is an integer between 1 and N, write an algorithm to find a duplicate. Your algorithm should run in linear time, use O(1) extra space, and may not modify the original array. Hint: pointer doubling.

我正试图从一本书中解决这个问题。在这种情况下，指针加倍意味着什么？这本书使用 Java，所以我假设这一定也适用于 Java，即使 Java 中没有指针的概念。

Answer 1

我认为我不能添加超出此网页内容的任何内容:

http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html

您的 O(n) 运行时间和 O(1) 空间的实际问题大约在页面的一半处得到解决，我认为必须将“指针加倍”作为最佳解决方案。解决问题的基本伪代码如下:

let i ← n, j ← n
do: i ← A[i], j ← A[A[j]]; until i = j
set j ← n
do: i ← A[i], j ← A[j]; until i = j
return i

虽然我会建议访问该网站，因为解释比我能给出的任何解释都详尽得多。