给定具有多个重复条目的阵列,重复输入O(N)时间和恒定空间

Question

我们给出了一个大小为N的数组,其中包含0到N-2范围内的整数,包括0和N-2.

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

我正在考虑获取阵列中所有entires的乘积和总和,以及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的循环寻找算法.特别是它告诉我们O(N)时间和O(1)空间中循环的"开始".