给定一个具有多个重复条目的数组，找到一个重复条目 O(N) 时间和常数空间

我们得到了一个大小为 N 的数组，其中包含 0 到 N-2 范围内的整数（包括 0 和 N-2）。

该数组可以有多个重复的条目。我们需要在 O(N) 时间和常量空间中找到重复条目之一。

我正在考虑取数组中所有条目的乘积和总和，以及 0 到 N-2 范围内所有数字的乘积和总和。

然后，总和的差值与乘积的除法将给出两个方程。如果只存在两个重复条目，则这种方法会起作用，但由于可能有两个以上，我认为我的方法失败了。

有什么建议么？

编辑：数组是不可变的。我意识到这是一条重要的信息，很抱歉我之前忘记包含此信息。

这是一个很好的治疗方法。在解决这一问题之前，它会先解决一些更简单的问题。

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

它包含一个当您可以修改输入数组时的解决方案，以及另一个当您不能修改输入数组时的解决方案。

简要总结以防链接失效：数组索引从 0 .. N-1 开始，数组值从 0 .. N-2 开始。因此，每个数组元素都可以被视为数组本身的索引（或“指针”）：i“指向”元素ra[i], ra[i]指着ra[ra[i]]等等。通过重复遵循这些指针，我最终必须进入一个循环，因为我们肯定不能永远不重新访问某个节点或其他节点。

现在，最后一个元素 N-1 没有被任何其他元素指向。因此，如果我们从那里开始并最终进入一个循环，那么沿途的某个地方一定有一个元素可以从两个不同的地方到达：我们第一次走的路线，以及作为循环一部分的路线。像这样的事情：

  N-1 -> a1 -> a2 -> a3
               ^       \
              /         v
            a6 <- a5 <- a4

在这种情况下，a2 可以从两个不同的地方到达。

但从两个不同位置可访问的节点正是我们要寻找的，即数组中的重复节点（两个不同的数组元素包含相同的值）。

那么问题是如何识别a2，答案是使用Floyd 的环路查找算法 http://en.wikipedia.org/wiki/Cycle_detection。特别是，它告诉我们在 O(N) 时间和 O(1) 空间中循环的“开始”。