查找数组中的重复项，而无需使用任何额外的空间 [英] Find duplicates in an array, without using any extra space

问题描述

给出一个包含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.

推荐答案

如果没有其他信息，这个问题似乎无法解决，因为这是

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)更多内存，并使用哈希表/

(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[i] , a[i+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支持)，但想法是，如果我们对问题进行建模作为代数计算树(这是一个合理的假设，不允许散列，并且可以使用恒定的空间)，然后，本·奥尔(Ben Or)在他的文章下界为了 ，但是这些文章得出的结论是在代数树计算模型下-整数相异性问题是Omega(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屋！