java - 在列表中查找所需条目的数量？

Question

设计一个算法，给定数组中的 n 个元素的列表，找到在列表中出现超过 n/3 次的所有元素。该算法应在线性时间内运行（ n >=0 ）

您应该使用比较并实现线性时间。没有散​​列/过多的空间/并且不使用标准的线性时间确定性选择算法？我觉得问题是自我阻塞？

Answer 1

提示：看看Boyer 和 Moore 的线性时间投票算法

脚步：

1. 在 0(n) 时间内使用中位数算法查找数组的中位数
2. 使用中值作为主元进行分区
3. 在a) 中值和第一个元素和 b) 中值和最后一个元素之间的每个部分中使用moore 的投票算法
   
   
4. 检查中位数是否是必需的元素。

有关解决此问题的更详细算法，您可以参考此文档。真的，这将非常有帮助。

有关更多答案，请参阅此类似帖子。