arrays - 在 O(log n) 时间内找到数组中的重复元素

Question

我知道类似的问题可能会被问很多次，但它与那些不同。

给定一个未排序的整数数组，其中1 to N-1包含一个重复元素（N是数组的大小，最大值是N-1由于重复元素）。找到重复元素的最佳方法是什么？如果可能的O(log n)话。`

我知道O(n)解决方案，但有什么办法可以及时解决这个问题O(log n)吗？

O(n) 解决方案：

1) Find sum of first N-1 natural numbers using N(N-1)/2, lets say it SUM1
2) Find sum of all the elements of the arrays, let say it SUM2

Duplicate = SUM2 - SUM1

Answer 1

它不能以次线性方式完成，数组未排序，因此您需要在最坏的情况下读取所有元素。

这种直觉非常通用，适用于许多处理未排序数组的算法，因为您的欺骗元素可能正在等待“超出界限”。

当然，同样的直觉不适用于排序数组的问题。

Answer 2

它不能在亚线性时间内完成。输入没有这样的属性（如排序数组）让您在 log(N) 时间内完成。