给定一个数组有多个重复条目，FND 1重复的条目O（N）的时间和空间不变 [英] Given an array with multiple repeated entries, fnd one repeated entry O(N) time and constant space

问题描述

我们已经给出大小为N的阵列，其中包含在范围0的整数N-2，包括两端。

We have been given an array of size N that contains integers in the range 0 to N-2, both inclusive.

阵列可以具有多个重复条目。我们需要找到重复的条目之一O（N）的时间和不断的空间。

The array can have multiple repeated entries. We need to find one of the duplicated entries in O(N) time and constant space.

我想的采取所有的数的乘积和所述阵列中的所有entires的总和，并将产物和总和在范围0到N-2。

I was thinking of taking the product and sum of all the entires in the array, and the product and sum of all the numbers in the range 0 to N-2.

然后，和的产品的差异化和分裂将会给我们两个方程。这种方法是有效的，如果它被赋予了只有两个重复的条目，但因为可以有两个以上的，我觉得我的做法失败。

Then, the difference of the sums and the division of the products would give us two equations. This approach would work if it were given that there are only two repeated entries, but since there can be more than two, I think my approach fails.

有什么建议？

编辑：数组是不可变的。我意识到，这是一条重要信息，我很抱歉，我忘了，包括这点。

The array is immutable. I realize that this is an important piece of information and I apologize that I forgot to include this earlier.

推荐答案

下面是一个不错的待遇。它通过解决这个之前的一些容易的问题。

Here's a nice treatment. It passes through some easier problems before addressing this one.

http://aperiodic.net/phil/archives/Geekery/找到重复的-elements.html

它包含了时，你可以修改输入阵列的解决方案，另一个是当你不能。

It contains a solution for when you can modify the input array, and another for when you can't.

小结在情况下，链接会消逝：数组索引从0运行.. N-1，和数组值运行0 ... N-2。因此，每个数组元素可以被视为一个索引（或指针）到阵列本身：元素我点元素 RA [我] ， RA [I] 指向 RA [RA [I]] 等上。通过反复以下这些指针，我必须最终进入一个循环，因为我们当然不能走永远没有重访某个节点或其他。

Brief summary in case the link ever dies: the array indexes run from 0 .. N-1, and the array values run 0 .. N-2. Each array element can therefore be considered as an index (or "pointer") into the array itself: element i "points to" element ra[i], ra[i] points to ra[ra[i]] and so on. By repeatedly following these pointers, me must eventually enter a cycle, because we certainly can't go forever without revisiting some node or other.

现在，在最后的元素，N-1，不被任何其他元件指向。因此，如果我们从那里开始，并最终进入一个循环，某处沿途必须有它可以从两个不同的地方到达一个元素：我们采取了第一次的路径，并且这是周期的一部分的路由。事情是这样的：

Now, the very last element, N-1, isn't pointed to by any other element. So if we start there and eventually enter a cycle, somewhere along the way there must be an element which can be reached from two different places: the route we took the first time, and the route which is part of the cycle. Something like this:

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

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

In this case, a2 is reachable from two different places.

但是，一个节点是从两个不同的地方访问是$ P $，我们正在寻找pcisely什么，阵列中的一个重复（包含相同的值两个不同的数组元素）。

But a node which is reachable from two different places is precisely what we're looking for, a duplicate in the array (two different array elements containing the same value).

接下来的问题是如何识别A2，答案是使用弗洛伊德的循环查找算法。尤其是，它告诉我们，启动循环的O（N）的时间和O（1）空间。

The question then is how to identify a2, and the answer is to use Floyd's cycle-finding algorithm. In particular it tells us the "start" of the loop in O(N) time and O(1) space.

这篇关于给定一个数组有多个重复条目，FND 1重复的条目O（N）的时间和空间不变的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！