algorithm - 在给定时间范围内查找多重集的模式(最大多样性)

Question

给定的问题:

多重集是其中某些元素出现多次然后一次的集合(例如 {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 的值。

[提示:使用基于列表中位数的分治策略。分而治之策略产生的子问题不能小于“一定”的大小 达到给定的时间限制。]

我们最初的解决方案:

我们的想法是使用摩尔多数算法来确定多重集是否包含多数候选者(例如，{a, b, b} 具有多数，b)。在确定这是真还是假之后，我们要么输出结果，要么使用给定算法(称为选择)找到列表的中值，并将列表分成三个子列表(元素小于和等于中值，元素大于中位数)。同样，我们将检查每个列表以确定是否存在多数元素，如果存在，这就是您的结果。

例如，给定多重集{a, b, c, d, d, e, f}

第 1 步:检查多数。没有找到，根据中位数拆分列表。

第 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(出现次数最多)。

Answer 1

如果您按照帖子中描述的那样以最直接的方式使用递归，它将不会具有所需的时间复杂度。为什么？让我们假设 answer 元素是最大的一个。然后它总是位于递归的右分支。但是我们首先调用左边的分支，如果所有元素在那里都是不同的，它可以走得更深(得到大小为 1 的片段，但我们不想让它们小于 M).

这是一个正确的解决方案:

让我们始终按照问题中的描述在每一步将数组分成三部分。现在让我们退到一边，看看我们有什么:递归调用形成一棵树。为了获得所需的时间复杂度，我们永远不应深入到答案所在的级别。为此，我们可以使用带队列的广度优先搜索而不是深度优先搜索来遍历树。就是这样。