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

Question

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

Answer 1

1. 及时找出中位数O(n)。
2. 使用 3 路分区基于该中值对数组进行分区。
3. 如果中值本身是必需的元素，则执行
   else
   在两个分区（中值的左侧和右侧）上应用多数元素算法。（在您的情况下，找到在 n/2 的数组中出现超过 n/4 次的元素）。两者都会O(n)及时运行。

总时间为3*O(n)=O(n)。
希望这可以帮助 ：）