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

标签 java arrays algorithm

我们得到了一个大小为 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/

相关文章:

java - 需要帮助在 Activity 加载和按下按钮时显示随机选择的图像

Confluence 的 C# 语法高亮显示

javascript - 无法通过将随机值从数组复制到对象来获得稳定的结果

algorithm - 是否可以使用统一差异来推断编辑距离?

java - Android map 应用程序未在设备中运行

Java程序找到字符串中出现次数最多的字符?

c - 数组和 scanf 问题;与 scanf 一起使用的值

c - 将文件 .txt 读取到数组并拆分

r - 在 R 中执行 SQP 算法

objective-c - 优化数组搜索,通过比较 Objective C 中的 2 个字符串进行搜索