给定的问题：
多集是其中一些元素出现不止一次的集合（例如{A，f，b，b，e，c，b，g，A，i，b}是多集）。元素是从一个完全有序的集合中提取的。呈现一个算法，当以多集作为输入时，找到在多集中出现次数最多的元素（例如，在{a，f，b，b，e，c，b，g，a，c，b}中，b出现次数最多）。算法应该在O（n lg n/M+n）时间内运行，其中n是多集中元素的数量，M是多集中元素出现的最高次数。请注意，您不知道M.的值
[提示：使用基于列表中值的分治策略。分治策略生成的子问题不能按顺序小于"特定"大小以达到给定的时限。]
我们的初步解决方案：
我们的想法是使用Moore的多数算法来确定多集是否包含多数候选者（例如{a，b，b}有多数，b）。在确定这是真是假之后，我们要么输出结果，要么使用给定的算法（称为Select）找到列表的中值，并将列表拆分为三个子列表（小于和等于中值的元素，以及大于中值的元素）。同样，我们会检查每个列表，以确定是否存在多数元素，如果存在，那就是您的结果。
例如，给定多集{a，b，c，d，d，e，f}
第一步：检查多数。未找到，请根据中位数拆分列表。
步骤2：L1={a，b，c，d，d}，L2={e，f}找到每个的多数。找不到，请再次拆分列表。
步骤3：L11={a，b，c}L12={d，d}L21={e}L22={f}检查每个元素的多数元素。L12返回d。在这种情况下，d是原始多集中出现次数最多的元素，因此是答案。
我们面临的问题是，这种类型的算法是否足够快，以及是否可以递归完成，或者是否需要终止循环。正如提示所说，子问题不能小于某个"特定"大小，我们认为它是M（出现次数最多）。
如果您像文章中描述的那样以最直接的方式使用递归，它将不会具有所需的时间复杂性。为什么？让我们假设答案元素是最大的一个。然后它总是位于递归的右分支中。但我们首先调用左分支，如果所有元素在那里都是不同的，那么它可以更深入（得到大小为1的片段，而我们不想让它们小于M）。
这里有一个正确的解决方案：
让我们在每一步都将数组分成三部分，如您的问题所述。现在让我们退一步，看看我们有什么：递归调用形成了一个树。为了获得所需的时间复杂性，我们永远不应该深入到答案所在的层次。为了实现这一点，我们可以使用带队列的广度优先搜索而不是深度优先搜索来遍历树。就是这样。
如果你想在现实生活中做到这一点，那么值得考虑使用哈希表来跟踪计数。这可以为每次哈希表访问分摊O（1）的复杂性，因此以下Python代码的总体复杂性为O（n）。
import collections
C = collections.Counter(['a','f','b','b','e','c','b','g','a','i','b'])
most_common_element, highest_count = C.most_common(1)[0]