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

Question

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

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

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

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

有什么建议吗？

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

Answer 1

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

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's cycle-finding algorithm .特别是它在 O(N) 时间和 O(1) 空间内告诉我们循环的“开始”。