algorithm - 在不使用任何额外空间的情况下查找数组中的重复项

Question

给定一个包含 n 个整数元素的数组，你将如何在不使用任何额外空间的情况下在 O(n) 时间内找出数组中是否存在重复项。

额外的空间意味着 O(n) 阶的额外空间。

Xor 运算符有任何帮助。

Answer 1

如果没有额外的信息，这个问题似乎无解，因为这是 Element Distinctness Problem ，在要求的时间内，您提供的限制无法解决。

你可以允许:

(1) 更多内存 并使用 hashtable/hashset并满足 O(n) 时间标准。 [迭代数组，检查一个元素是否在哈希表中，如果是，你有欺骗，否则 - 将元素插入表中并继续]。

(2)更多时间，对数组[O(nlogn)]进行排序，满足亚线性空间条件。 [排序后，遍历数组，对于每个 a[i] 、 a[i+1] ，检查它们是否相同。如果你没有找到相同的一对，你就没有被骗]

编辑:这个声明的证明有点冗长，并且需要这里不支持的数学符号(旁注:我们确实需要 tex 支持)，但我们的想法是如果我们对我们的问题进行建模作为代数计算树(这是一个合理的假设，当不允许散列，并且空间不变时，Ben Or 在他的文章中证明了 Lower Bounds For Algebraic Computation Trees (1983) (发表于著名的 ACM)，该模型下的元素差异性是 Omega(nlogn) 问题。 Lubiw 在 1991 年表明，同样的结论也适用于将我们自己限制为整数:A Lower Bound forthe Integer Element Distinctness Problem , 但这些文章的结论是在代数树计算模型下——整数相异性问题是Omega(nlogn)问题。