One*_*ree 6 algorithm binary search
在O(n)中很容易找到最常出现的元素.是否有更快的算法(O(logn))来做到这一点？(给定数组已排序)
Iva*_*nov 10
是不可能的.下面不是一个严格的证据(严格的下限证明一般很难),但一个理智的推理.
假设你的数组总是看起来像1, 2, 3, 4, 5, 6, ..., n.然后用一个前一个数字的出现替换一些数字:1, 2, 3, 3, 5, ... n.现在在除了一个位置之外的a[i] = i所有新数组中i.
为了找到最常见的元素,您必须检查所有位置并检查那里的不规则性.请注意,只有一个不规则性,如果你查看数组的任何其他元素,你可以不说它的位置.因此,这个问题并不比one在一个零和一个零的布尔数组中找到,这需要线性时间.