algorithm - 寻找最频繁的元素

Question

有几种颜色的球。对于一种特定的颜色，有超过一半的球具有这种颜色（>n/2）。我怎样才能找到这种颜色只需要 O(n) 运行时间？

Answer 1

您可以使用Boyer-Moore 多数算法

Answer 2

找出每个球的颜色并计算出来。如果您只想找到最频繁的，这似乎根本不是排序。只需计算每种颜色的球数。您可以使用哈希表，关键是颜色，然后迭代该点。还要跟踪颜色。

编辑：再次阅读后，我意识到它没有回答问题。

A）您可以通过迭代每种可用颜色（假设您正在制作颜色列表）在最后进行跟踪，因为将有少于 n 次比较，在最坏的情况下它将是 O(n)。

B) 当你计算球数时，记录最大的数。每当它被击败时，将其替换为具有最高计数的当前颜色。您可能希望跟踪颜色以及最高数字。这样，您将在每次运行时进行比较。这又将是 O(n)，但会有更多的比较。