9

假设，给定一个 n 元素多重集 A（未排序），我们需要一个 O(n) 时间算法来确定 A 是否包含多数元素，即在 A 中出现超过 n/2 次的元素。它是使用线性时间选择算法很容易在 O(n) 时间内解决这个问题（否则答案是“没有多数”）。现在考虑这个问题的以下概括：给定 A 和一个整数 k < n，我们想要一个算法来确定 A 是否包含一个在其中出现超过 n/k 次的值（如果存在许多这样的值，那么这就足够了找到其中之一）。为此设计一个算法，并将其复杂性分析为 n 和 k 的函数。你在这个问题上的成绩将取决于你的算法有多快（当然它也必须是正确的）。对于 O(kn) 时间算法，部分计分 10 分，对于 O(n log k) 时间算法，全部计分。

现在我已经为这个问题提出了 2 个解决方案，但都不能完全满足 O(n log k) 的要求。我立即看到我可以使用 O(n log n) 算法对数组进行排序，然后查看是否有任何元素线性重复超过 n/k 次，但这是 O(n log n) 而不是 O(n log k)

我还发现并在一定程度上理解了一种 O(nk) 方法，方法是创建一个与输入具有相同数据类型的数组和一个 k 长的 int。然后将每个元素放入一个空元素中，增加它的计数器，或者如果它匹配其中的一个元素，增加它的计数器，直到我们到达第 k+1 个唯一元素，此时你将所有计数器减 1，直到一个达到 0，此时它是被认为是空的，可以将新元素放入其中。依此类推，直到输入数组的末尾。然后检查我们完成后剩下的所有元素，看看它们是否出现超过 n/k 次。但由于这涉及检查 n 个原始元素与所有 k 个新数组元素，它是 O(nk)。关于如何在 O(n log k) 中解决这个问题的任何提示？我认为 O(nk) 算法符合他希望我们思考的方式，但我

4

3 回答 3

7

您描述的方法只需要递归使用。

请记住，select将小于或等于中位数的元素移动到中位数的左侧。

如果A是大小n。

求 的中位数A。现在找到由中位数划分的两个子多组长度中的每一个的n/2中位数。找到由中位数划分的四个子多组长度中的每一个的n/4中位数。继续递归直到叶子是 length n/k。现在递归树的高度是O(lgk)。在递归树的每一层，都有O(n)操作。如果存在一个至少重复多次的值，n/k那么它将位于其中一个具有子多集k长度的值中。n/k最后的操作也在O(n). 所以你得到了请求的运行时间O(nlgk)。

于 2012-08-24T22:04:05.840 回答
2

O(kn) 算法

我想知道 O(kn) 算法是否可能更符合以下原则：

  1. 查找 k 个规则间隔的元素（使用与中位数类似的线性选择算法）
  2. 计算你为这些中的每一个获得了多少匹配

想法是，如果一个元素出现 n/k 次，它必须是其中之一。

O(nlogk) 算法

也许您可以将问题中提出的方案与树结构一起使用来保存 k 个元素。那么这将意味着搜索匹配项只会是 log(k) 而不是 k，对于整体 O(nlogk)？

请注意，您应该将树用于第一遍（您正在寻找我们需要考虑的 k 个候选者）和第二遍计算每个元素的确切计数。

另请注意，您可能希望使用惰性评估方案来递减计数器（即标记需要递减的整个子树并仅在下次使用该路径时传播递减量）。

O(n) 算法

如果您在现实生活中遇到这种情况，我会考虑使用基于哈希的字典来存储直方图，因为这应该会提供一个快速的解决方案。

例如，在 Python 中，您可以在（平均）O(n) 时间内使用

from collections import Counter
A=[4,2,7,4,6]
k=3

element,count = Counter(A).most_common()[0]

if count>=len(A)//k:
    print element
else:
    print "there is no majority"
于 2012-08-24T21:49:57.120 回答
0

我不知道你是否看过这个，但它可能有助于给你一些想法：

假设您知道数组 L 中有多数元素。

查找元素的一种方法如下：

Def FindMajorityElement(L):

    Count = 0

    Foreach X in L

        If Count == 0
            Y = X

        If X == Y
            Count = Count + 1
        Else
            Count = Count - 1

    Return Y

O(n) 时间，O(1) 空间

于 2012-08-24T22:09:44.690 回答