在给定时间范围内查找多重集的模式（最大多样性）
Find mode of a multiset in given time bound (most multiplicity)
给出的问题：
多重集是其中某些元素出现不止一次的集合（例如 {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 是 multiset 中元素的数量，M 是元素在 multiset 中出现的最高次数。请注意，您不知道 M.
的值
[提示：使用基于列表中位数的分而治之策略。分而治之策略产生的子问题不能小于“一定”的大小
达到给定的时间限制。]
我们的初步解决方案：
我们的想法是使用摩尔多数算法来确定多重集是否包含多数候选者（例如，{a, b, b} 具有多数，b）。在确定这是真还是假之后，我们要么输出结果，要么使用给定算法（称为 Select）找到列表的中值，并将列表分成三个子列表（小于和等于中值的元素，和大于中位数的元素）。同样，我们将检查每个列表以确定是否存在多数元素，如果存在，这就是您的结果。
例如，给定多重集 {a, b, c, d, d, e, f}
第 1 步：检查多数。 None找到，根据中位数拆分列表。
第 2 步：L1 = {a, b, c, d, d}，L2 = {e, f} 找出每个的多数。 None找到，再次拆分列表。
第 3 步：L11 = {a, b, c} L12 = {d, d} L21 = {e} L22 = {f} 检查每个的多数元素。 L12 returns d.在这种情况下，d 是原始多重集中出现次数最多的元素，因此就是答案。
我们遇到的问题是这种算法是否足够快，以及是否可以递归完成或者是否需要终止循环。正如提示所说，子问题不能小于 'certain' 大小，我们认为这是 M（出现次数最多）。
如果您想在现实生活中这样做，值得考虑使用散列 table 来跟踪计数。这可以为每个哈希 table 访问分摊 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]
如果您按照 post 中所述以最直接的方式使用递归，它将不会具有所需的时间复杂度。为什么？让我们假设 answer 元素是最大的一个。然后它总是位于递归的右分支。但是我们首先调用左边的分支，如果所有元素在那里都是不同的，它可以更深入（得到大小 1，但我们不想让它们小于 M）。
这是一个正确的解决方案：
让我们始终按照问题中的描述在每一步将数组分成三部分。现在让我们退到一边，看看我们有什么：递归调用形成一棵树。为了获得所需的时间复杂度，我们永远不应深入到答案所在的级别。为此，我们可以使用带队列的广度优先搜索而不是深度优先搜索来遍历树。而已。
给出的问题：
多重集是其中某些元素出现不止一次的集合（例如 {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 是 multiset 中元素的数量，M 是元素在 multiset 中出现的最高次数。请注意，您不知道 M.
的值[提示：使用基于列表中位数的分而治之策略。分而治之策略产生的子问题不能小于“一定”的大小 达到给定的时间限制。]
我们的初步解决方案：
我们的想法是使用摩尔多数算法来确定多重集是否包含多数候选者（例如，{a, b, b} 具有多数，b）。在确定这是真还是假之后，我们要么输出结果，要么使用给定算法（称为 Select）找到列表的中值，并将列表分成三个子列表（小于和等于中值的元素，和大于中位数的元素）。同样，我们将检查每个列表以确定是否存在多数元素，如果存在，这就是您的结果。
例如，给定多重集 {a, b, c, d, d, e, f}
第 1 步：检查多数。 None找到，根据中位数拆分列表。
第 2 步：L1 = {a, b, c, d, d}，L2 = {e, f} 找出每个的多数。 None找到，再次拆分列表。
第 3 步：L11 = {a, b, c} L12 = {d, d} L21 = {e} L22 = {f} 检查每个的多数元素。 L12 returns d.在这种情况下，d 是原始多重集中出现次数最多的元素，因此就是答案。
我们遇到的问题是这种算法是否足够快，以及是否可以递归完成或者是否需要终止循环。正如提示所说，子问题不能小于 'certain' 大小，我们认为这是 M（出现次数最多）。
如果您想在现实生活中这样做，值得考虑使用散列 table 来跟踪计数。这可以为每个哈希 table 访问分摊 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]
如果您按照 post 中所述以最直接的方式使用递归，它将不会具有所需的时间复杂度。为什么？让我们假设 answer 元素是最大的一个。然后它总是位于递归的右分支。但是我们首先调用左边的分支，如果所有元素在那里都是不同的，它可以更深入（得到大小 1，但我们不想让它们小于 M）。
这是一个正确的解决方案：
让我们始终按照问题中的描述在每一步将数组分成三部分。现在让我们退到一边，看看我们有什么：递归调用形成一棵树。为了获得所需的时间复杂度，我们永远不应深入到答案所在的级别。为此，我们可以使用带队列的广度优先搜索而不是深度优先搜索来遍历树。而已。