查找数组中的重复 [英] Find duplicates in an array

问题描述

给定n个整数元素如何，你会发现是否有O（n）时间数组中的重复，而无需使用任何额外的空间阵列。

Given an array of n integer elements how will you find whether there are duplicates in the array in O(n) time without using any extra space.

使用额外的空间，这意味着为了为O（n）的额外空间。

With extra space it means extra space of order O(n).

是否以任何方式XOR运算符的帮助。

Does the Xor operator help in any way.

推荐答案

如果没有更多的信息，这个问题似乎是unsolveable，因为这是在的元素清晰与问题 ，这是unsolveable与您提供的限制，在规定的时间。

If there is no additional information, this question seems to be unsolveable, as this is the Element Distinctness Problem, which is unsolveable with the restrictions you provided, in the required time.

您可以允许：

（1）更多的内存并使用哈希表 /的 HashSet的并满足O（n）的时间标准。 [遍历数组，检查元素是否是哈希表中，如果你有愚弄，否则 - 插入元素到表中，然后继续。

(1) more memory and use a hashtable / hashset and meet the O(n) time criteria. [iterate the array, check if an element is in the hash table, if it is you have dupes, otherwise - insert the element into the table and continue].

（2）更多的时间，排序数组[O（nlogn）]，并满足亚线性空间的标准。 [整理后，遍历数组，并为每个 A [1]，A [1 + 1] ，检查它们是否相同。如果你没有找到相同的对，你没有愚弄]

(2) more time, sort the array [O(nlogn)] and meet the sub-linear space criteria. [After sorting, iterate over the array, and for each a[i] , a[i+1] , check if they are identical. If you did not find an identical pair, you have no dupes]

修改：该证明这种说法是有点漫长，需要在此处未支持的数学符号（旁注：我们真的需要TEX支持），但这个想法是，如果我们的模型是我们的问题作为代数计算树（这是当没有散列允许公平假设，并在出处置恒定空间），然后，本或者证明在他的文章中的下限的代数运算树（1983）（发表于prestiged ACM），该元素分辩率欧米茄（nlogn）在这种模式下的问题。 Lubiw表明，在相同的结论时，我们自己限制为整数，1991年也同样适用：<一href="http://www.ic.unicamp.br/~rezende/ensino/mo619/Lubiw,ALowerBoundForIntegerElementDistinctness.pdf">A下界 整数元素清晰与问题，但这些文章得出结论：代数树计算模式下 - 整数清晰与问题是欧米茄（nlogn）问题

EDIT: The proof for this claim is a bit lengthy, and needs mathematical notation that are not supported here (sidenote: we really need tex support), but the idea is if we model our problem as an Algebraic Computation Tree (which is a fair assumption when no hashing is allowed, and constant space at out disposal), then, Ben Or proved in his article Lower Bounds For Algebraic Computation Trees (1983) (published in prestiged ACM), that element distinctness is Omega(nlogn) problem under this model. Lubiw showed that the same conclusion also applies when limiting ourselves to integers in 1991: A Lower Bound for the Integer Element Distinctness Problem, but these articles conclude that under the algebraic tree computation model - Integer Distinctness Problem is Omega(nlogn) Problem.

这篇关于查找数组中的重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！