如果确定一个数组的k-大多数元素 [英] Determining if an array has a k-majority element

问题描述

假设，给予正元多集A（不排序），我们 想要一个O（n）时间的算法用于确定是否包含大部分元素，也就是说， 出现多于n / 2次A中的元件可以很容易通过为解决这个在O（n）的时间 采用线性时间选择算法通过网络nding中位数（称之为X），然后计算 多少x次发生在并返回为广大如果计数大于n / 2 （否则，答案是没有多数）。现在考虑下面的概括 问题：给定一个和一个整数k＆LT; N，我们希望有一个算法来决定 A是否包含发生多于n / k次在它的值（如果许多这样的值 存在，那么它是足够的科幻十二次其中之一）。设计一个算法做这一点， 分析其复杂性，因为n和k的一个函数。你在这个问题上的成绩将取决于 如何快速的算法是（当然也必须是正确的）。 10分部分贷款，给出了一个O（KN）时间的算法，全面的信用是一个O（N日志K）时间的算法。

Suppose that, given an n-element multiset A (not sorted), we want an O(n) time algorithm for determining whether A contains a majority element, i.e., an element that occurs more than n/2 times in A. It is easy to solve this in O(n) time by using the linear-time selection algorithm by finding the median (call it x), then counting how many times x occurs in A and returning it as the majority if the count exceeds n/2 (otherwise the answer is "there is no majority"). Now consider the following generalization of the problem: Given A and an integer k < n, we want an algorithm that determines whether A contains a value that occurs more than n/k times in it (if many such values exist, then it is enough to find one of them). Design an algorithm for doing this, and analyze its complexity as a function of n and k. Your grade on this question will depend on how fast your algorithm is (of course it also has to be correct). Partial credit of 10 points is given for an O(kn) time algorithm, full credit is for an O(n log k) time algorithm.

我现在已经拿出2解决方案的问题，但没有完全满足 为O（n日志k）的要求。我立刻看到我可以使用为O（n log n）的算法，然后再通过并看看是否有任何元素多于n / k次线性重复以上排序数组但这是O（n log n）的不是O（N日志K）

now I have come up with 2 solutions for the problem but neither fully satisfy the O(n log k) requirement. immediately i saw that i could sort the array using a O(n log n) algorithm then go through and see if any elements repeat more than n/k times linearly but that is O(n log n) not O(n log k)

我还发现，有些理解的O（NK）methood通过相同的数据类型作为输入数组和一个int值，为k，长做。然后将每个元素放入一个空的元素递增的计数器，或者如果它在那里的递增计数器，直到我们到达此时您按1递减所有计数器直到有第k + 1独特的元素相匹配的一个元素达到0此时它是认为是空的和新的元件可以放置在它。等，直到输入数组的末尾。然后选中全部离开后，我们已经完成了，看他们是否出现超过N / K倍的元素。但由于这涉及到检查对新的数组中的元素所有的k的N个原始元素是O（NK）。如何做到这一点问题为O（n日志k）的任何提示？我认为，O（NK）算法是沿着他希望我们如何思考的线条，但我不知道在哪里何去何从。

I also have found and somewhat understood a O(nk) methood done by making an array of the same data type as the input and an int that is k long. then putting each element into an empty element incrementing its counter or if it matches one element in there incrementing its counter till we reach the k+1th unique element at which point you decrement all the counters by 1 till one reaches 0 at which point it is considered empty and the new element can be placed in it. and so on till the end of the input array. then checking all the elements left after we are done to see if they occur more than n/k times. but since this involves checking the n original elements against all k of the new arrays elements it is O(nk). any hints on how to do this problem in O(n log k)? I think the O(nk) algorithm is along the lines of how he wants us to think but I'm not sure where to go from here.

推荐答案

这是你介绍的方法只需要嵌套使用。

The method that you described just needs to be used recursively.

记住，选择移动是小于或等于中位数的中位数左侧的元素。

Remembering that select moves the elements that are less or equal to the median to the left of the median.

如果 A 是大小 N 。

查找 A 的中位数。 现在发现每两个子多套长度的中位数 N / 2 这是由平均分配。 找到每个的四个子多套长度的中位数 N / 4 这是由位数划分。 继续递归，直到叶子长度 N / K 的。 现在递归树的高度 O（LGK）。 在递归树的每一层，有 O（N）操作。 如果存在重复至少 N / K 倍的数值，然后它会在一个 这些 K 与的长度为N / K 子多套。 最后的操作也在完成为O（n）。 所以，你得到 0的请求的运行时间（nlgk）。

Find the median of A. Now find the median of each of the two sub multi-sets of length n/2 that were partitioned by the median. Find the median of each of the four sub multi-sets of length n/4 that were partitioned by the medians. Continue recursively until the leaves are of length n/k. Now the height of the recursive tree is O(lgk). On each level of the recursive tree, there are O(n) operations. If there exist a value that is repeated at least n/k times then it will be in one of these k with length of n/k sub multi-sets. The last operations is also done in O(n). So you get the requested running time of O(nlgk).

这篇关于如果确定一个数组的k-大多数元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！