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

Question

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

给定一个未排序的整数数组，其值为 1 到 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

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

这种直觉非常普遍，适用于许多处理未排序数组的算法，因为你的 dupe 元素可能在你拥有的“界限后面”等待。

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