在不使用任何额外空间的情况下查找数组中的重复项 [英] 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).

异或运算符是否有任何帮助.

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) 更多内存并使用哈希表/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[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 在他的文章 代数计算树的下界 (1983)(发表于著名的 ACM)，该元素的独特性是该模型下的 Omega(nlogn) 问题.Lubiw 表明，同样的结论也适用于 1991 年将我们限制为整数时的情况:下界为了整数元素相异性问题，但这些文章得出的结论是在代数树计算模型下——整数相异性问题是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屋！