查找元素在n元素数组中是否出现n/4次

Question

我被问到这个问题.我尝试使用多数元素方法,但它对我不起作用.请提供一些提示.

Answer 1

1. O(n)及时找出中位数.
2. 使用3向分区基于该中值对数组进行分区.
3. 如果中位数本身是必需的元素,则完成
   其他
   在分区(中间的左侧和右侧)应用多数元素算法.(在你的情况下,找到在n/2数组中出现超过n/4次的元素).两者都会O(n)及时运行.

总时间是3*O(n)=O(n).
希望这可以帮助 :)