确定数组是否具有k-多数元素
假设给定一个n元素多集A (未排序)，我们想要一个O(n)时间算法来确定A是否包含多数元素，即在A中出现超过n/2次的元素。很容易通过使用线性时间选择算法在O(n)时间内解决这个问题，方法是对中位数进行fi(称为x)，然后计算x在A中出现的次数，如果计数超过n/2，则返回它作为多数(否则答案是“没有多数”)。现在考虑以下问题的推广:给定A和一个整数k< n，我们需要一个算法来确定A是否包含在其中出现超过n/k次的值(如果存在许多这样的值，则足以对其中的一个值执行fi操作)。为此设计一个算法，并分析其复杂度作为n和k的函数。你在这个问题上的分数将取决于你的算法有多快(当然，它也必须是正确的)。对于O(kn)时间算法，给予10分的部分积分，对于O(n log k)时间算法，给予全部积分。
现在我已经为这个问题提出了两个解决方案，但都没有完全满足O( now )的要求。我立即发现我可以使用O( not )算法对数组进行排序，然后查看是否有任何元素线性重复超过n/k次，但这是O(Not)而不是O(Not)
我还发现了一种O(nk)方法，它是通过创建一个与输入数据类型相同的数组和一个k长的int数组来实现的。依此类推，直到输入数组的末尾。然后检查我们完成后剩下的所有元素，看看它们是否出现了超过n/k次。但由于这涉及到对照所有k个新数组元素检查n个原始元素，因此它是O(nk)。关于如何在O(n log k)中解决这个问题，有什么建议吗？我认为O(nk)算法是沿着他希望我们如何思考的方向进行的，但我不确定从哪里开始。
回答 3
Stack Overflow用户
发布于 2012-08-25 06:04:06
您所描述的方法只需要递归使用。
请记住，select会将小于或等于中位数的元素移动到中位数的左侧。
如果A的大小为n。
求A的中位数。现在找出由中位数划分的长度n/2的两个子多集中的每一个的中位数。找出由中值划分的长度为n/4的四个子多集合中每一个的中位数。递归地继续，直到叶子的长度为n/k。现在递归树的高度是O(lgk)。在递归树的每一层上，都有O(n)操作。如果存在重复至少n/k次的值，则它将在这些k之一中，长度为n/k子多集。最后的操作也是在O(n)中完成的。因此，您可以获得O(nlgk)所需的运行时间。
Stack Overflow用户
发布于 2012-08-25 05:49:57
O(kn)算法
我想知道O(kn)算法是否更类似于：
- 查找k个规则间隔的元素(使用类似于中值的线性选择算法)
- 计算这些
中的每一个得到的匹配数
其思想是，如果一个元素出现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"Stack Overflow用户
发布于 2012-08-25 06:09:45
我不知道你是否看过这篇文章，但它可能会给你一些想法：
假设您知道数组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 YO(n)时间，O(1)空间
https://stackoverflow.com/questions/12116788
复制相似问题
腾讯云开发者
