UOJ Logo Alextokc的博客

博客

绝对众数问题

2017-07-26 11:57:55 By Alextokc

读了一本叫做《啊哈!算法》的书的第九章:还能更好吗---微软亚洲研究院面试。感觉绝对众数问题的确有趣,可以通过反证的思维方式解决这类问题。也许就像知乎上的一个话题关于人类的大脑有哪些天生的设计缺陷我们大脑所习惯的运作方式其实不大支持严格的逻辑判断是导致大多数人第一次看到这类问题无法快速解决的原因。

比如请问以下的两个选项哪个选项更可能成立。 已知S君非常喜欢画画,

A. S君喜欢游泳 B. S君有许多绘画方面的朋友并且喜欢游泳。

显然A是正确的,但大多数人选的却是B,这也说明了人类大脑并不大支持严格的逻辑判断。

好,言归正传。如何解决这个绝对众数问题呢?题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2456

最简单的方法应该是用个双重循环,时间复杂度为$O(n^2)$,相信这样的算法绝大多数人都能想到。既然是最简单的算法,往往也不是最优秀的算法。

那有没有更快更好的方法呢?显然是有的。 第二种方法是将数组排个序,当然数组的下标从0开始,那么$n/2$的位置显然是绝对众数。听到这,也许有人不能一下子理解为什么下标为$n/2$所代表的数显然是绝对众数,是这样的:比如有n个数字,假设n是偶数且等于10,那么就有$10/2+1=6$个绝对众数,因为说了有一个数出现的次数超过50%。可以假设两种极端情况,一种是绝对众数都最靠数组的左边(即下标0),一种最靠右,一个长度为10的数组中6个连续的数最靠左或者最靠右会发现这两种情况都满足数组下标$n/2$所代表的数是绝对众数,这其实很显然,也就是说如果这6个连续的数不在最左不在最右唯一的可能就是绝对众数们更加靠近下标$n/2$,奇数同理。

由于排序算法的时间复杂度可以做到$O(nlogn)$,绝对众数问题到此为止也可以做到$O(nlogn)$。

那有没有线性的算法呢?考虑到无法做到比线性算法更优因为仅读入n个数字的时间复杂度也已经是线性的。

第一种容易想到的线性做法类似于桶排序,但如果数的空间跨度很大比如1,10000,10000000怎么办?很简单离散化一下即可,用C++中的unordered_map很容易实现。

第二种方法相信聪明的读者在前面已经考虑到排序真正的目的究竟是为了使数连续还是让数按照顺序排列,可以说更多的显然是使数连续,为什么这么说呢?因为即便数组里的数字大小并无顺序但只要数字是连续的就可以做到数组中第$n/2$位置是绝对众数。

但是否也可以通过求第$n/2$大的数来求出正确答案呢,显然可以,没错,第$n/2$大的数就是绝对众数。为什么这么说? 因为排序后位置处于最中间的数一定是绝对众数那绝对众数也一定是排序后在最中间的数,两者等价。确定的有BFPRT算法可以在严格线性的时间复杂度内解决问题。

最后一种是我见过的最妙的解法,可以说比前面所有的方法都显得贴近本质,也只有这种方法可以解决bzoj 2456(除非你通过java等语言钻空子),即考虑到一定有数的出现次数超过50%,那么即便是所有的绝对众数和非绝对众数一一抵消了最后留下来的仍然会是一个绝对众数,所以最后剩下的数一定是绝对众数。这种解法连数组都不用,几个变量即可。

所以解决这类问题可以用类似于"为什么一个人投票数超过50%这人就直接当选? 因为剩下的投票数不可能超过50%,如果超过50%,总量就超过了100%,那显然是不成立的"这种反证的思维方式。

备注:众数(mode)指一组数据中出现次数最多的数据值。例如{2,3,3,3}中,出现最多的是3,因此众数是3,众数可能是一个数,但也可能是多个数。数学里并没有绝对众数这种说法,在此,绝对众数的定义见bzoj 2456

评论

bzoj
许多地方打错别字了
zx2003
为什么已知S君非常喜欢画画,就显然S君喜欢游泳是正确的?只能说A比B更可能成立吧?
zhouyi
洛谷月赛出过一道绝对众数这个idea的题目, 叫做总统选举
WrongAnswer
IOI2015出过一道绝对众数这个idea的题目, 叫做towns。
negiizhao
median of medians找分位数是严格线性的
bzoj
最后的定义不对吧,比如1 2 3 4 4,其中4是唯一众数,但不是绝对众数

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。