algorithm - 给定一个排序的整数数组，找到 log(n) 中最常出现的元素

Question

在 O(n) 中很容易找到出现频率最高的元素。有没有更快的算法(O(logn))来做到这一点？ (假设数组已排序)

Answer 1

这是不可能的。以下不是严格的证明(严格的下界证明通常很难)，而是合理的推理。

假设您的数组总是看起来像 1, 2, 3, 4, 5, 6, ..., n。然后用之前出现的数字替换一些数字:1, 2, 3, 3, 5, ... n。现在在新数组 a[i] = i 中，除了一个位置之外的所有 i。

为了找到出现频率最高的元素，您必须检查所有位置并检查那里的不规则性。请注意，只有一处不规则，如果查看数组的任何其他元素，则无法说明其位置。因此，这个问题并不比在 1 和 0 的 bool 数组中找到一个 one 更容易，这需要线性时间。