趣题：用线性时间查找众数

十 29

万圣节快乐～为了迎接万圣节，我来分享一道巧题。

我们定义众数为一个元素个数为n的序列里面出现次数大于n div 2的元素。显然，一个序列不一定有众数。那么，我们要如何寻找一个序列的众数呢？

如果我要说的是O（nlogn）的排序算法，那就太没有意思了～
而且不能有计数排序之类的基于记录地址的算法——假如我举办一个名为“你最喜欢的数”的投票，那么我会将票投给“e”，有可能寺雷颠投给“π”……那么这样的元素是计数排序等所不能处理的。

接下来，我不禁要问，难道就没有比O(nlogn)更加敏捷的算法了么？
我给WebberYoung小牛看了这道题，结果他受今年的初赛完形题的影响，一直在用改编快排以找第K大数的思想，结果陷进了分治的死潭……先说下他的想法：如果存在众数，那么整个序列中大小处于中间的数就是众数，当我们找出了这个数，再扫描一遍即可。但是这样的算法在最坏情况下会是O(nlogn)的。

下面给出的算法很精彩，在处理元素方面只用到了等号或不等号——也就是说，连比较运算都没有用上。

答案：如果你能够意识到这个隐藏得比较好的性质，那么你就成功了：对于一个序列中的两个元素x和y，如果两者不相等，那么删除这两个元素后的序列中的众数仍然是原序列中的众数。其正确性是无比显然的。这样，我们现在就可以得到一个显然的算法了：扫描序列，进行删除操作，然后再次扫描以验证剩下的那个元素是否够多。
这里是深蓝邀请赛的标程。
这样，O(n)的算法就出来了。这里的比较次数是2n-2次，但是据说存在比较次数为 3n/2+1的最优解……如果大牛们有优化的方法，希望能告诉我。

PS：这题的来源比较奇特：《算法引论》6.10。这个《算法引论》不是山寨过的《算法导论》，作者为Udi Menber，全书详细地介绍了如何利用归纳这一重要思想进行算法设计。

本文由严酷的魔王创作，转载或引用前请联系我们。