算法查找数组中的三个多数元素

Question

假设在非排序数组中有三个元素,所有这些元素都是元素总数的四分之一以上.

找到这些元素的最有效方法是什么？这两个问题的非在线和在线版本.

谢谢!

编辑

我所指的非在线版本是:这个数组是完整的.在线版本意味着数组元素一次出现一个.

除了时间复杂性之外,我还要求空间紧张.

免责声明:这不是家庭作业!我认为这是研究水平的问题.

Answer 1

记住最多三个元素,以及计数器.

1. 记住第一个元素,设置count1 = 1
2. 扫描直到找到第一个不同的元素,每次出现元素1时增加count1
3. 记住第二个elemt,设置count2 = 1
4. 扫描,直到找到与elem1和elem2不同的第一个元素,递增count1或count2,具体取决于您看到的元素
5. 记住第三个元素,设置count3 = 1
6. 继续扫描,如果元素是被记住的元素之一,则增加其计数,如果没有记住,则减少所有三个计数; 如果计数降至0,则忘记该元素,转到步骤1,3或5,具体取决于您忘记了多少元素
7. 如果你有三个元素严格超过数组中元素数量的四分之一,那么最终会有三个记忆元素,每个元素都带有正数,这些元素是三个多数元素.

小的恒定额外空间,O(n),无排序.

Answer 2

创建条目的直方图，对其进行排序，并取三个最大的条目。