假设给定一个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)算法与他希望我们思考的方式一致,但我不确定从何处开始.
这个问题是Skiena的4-11.找到多数元素的解决方案 - 重复超过一半是多数算法.我们可以用它来查找重复n/4次的所有数字吗？