假设给定一个n元素多重集A(未排序),我们需要一个O(n)时间算法来确定A是否包含多数元素,即在A中出现超过n/2次的元素.它是通过使用线性时间选择算法,通过找到中位数(称之为x),然后计算在A中出现x的次数并在计数超过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)
我也发现并且稍微理解了通过使用与输入相同的数据类型的数组和k为long的int来完成O(nk)方法.然后将每个元素放入一个空元素中递增其计数器,或者如果它匹配一个元素递增其计数器直到我们到达第k + 1个唯一元素,此时你将所有计数器递减1直到一个达到0,此时它是被认为是空的,新元素可以放在其中.依此类推,直到输入数组结束.然后检查完成后剩下的所有元素,看它们是否出现超过n/k次.但由于这涉及针对新数组元素的所有k检查n个原始元素,因此它是O(nk).关于如何在O(n log k)中解决这个问题的任何提示？我认为O(nk)算法与他希望我们思考的方式一致,但我不确定从何处开始.
您描述的方法只需递归使用.
记住,select将中位数小于或等于中位数的元素移动到中位数的左侧.
如果A是大小n.
找到中位数A.现在找到n/2由中位数划分的两个子多组长度中的每一个的中位数.找出n/4由中位数划分的四个子多组长度中的每一个的中位数.递归地继续,直到叶子长n/k.现在递归树的高度是O(lgk).在递归树的每个级别上,都有O(n)操作.如果存在至少重复一次的值,n/k那么它将在其中一个中k具有n/k子多组的长度.最后的操作也是在O(n).所以你得到了所要求的运行时间O(nlgk).
我想知道 O(kn) 算法是否可能更符合以下原则：
这个想法是，如果一个元素出现 n/k 次，它一定是其中之一。
也许您可以将问题中提出的方案与树结构一起使用来保存 k 个元素。这意味着对于总体 O(nlogk) 来说，搜索匹配项将仅是 log(k) 而不是 k？
请注意，您应该在第一遍（您找到我们需要考虑的 k 个候选者）和第二遍计算每个元素的确切计数时使用该树。
另请注意，您可能希望使用惰性求值方案来递减计数器（即标记需要递减的整个子树，并仅在下次使用该路径时传播递减量）。
如果您在现实生活中遇到这种情况，我会考虑使用基于哈希的字典来存储直方图，因为这应该提供快速解决方案。
例如，在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"