我们得到了一个大小为 N 的数组,其中包含 0 到 N-2 范围内的整数,包括两者。
数组可以有多个重复项。我们需要在 O(N) 时间和常数空间中找到重复条目之一。
我正在考虑取数组中所有整数的乘积和总和,以及 0 到 N-2 范围内所有数字的乘积和总和。
然后,总和的差和乘积的除法将给出两个方程。如果假设只有两个重复条目,则此方法会起作用,但由于可以有两个以上,我认为我的方法失败了。
有什么建议吗?
编辑:数组是不可变的。我意识到这是一条重要的信息,我很抱歉之前忘记包含它。
最佳答案
这是一个不错的治疗方法。在解决这个问题之前,它会先解决一些更简单的问题。
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) 空间内告诉我们循环的“开始”。
关于java - 给定一个包含多个重复条目的数组,找到一个重复条目 O(N) 时间和常数空间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4234027/