直接上板子：洛谷P2397 yyy loves Maths VI (mode)
找 \(n\) 个数中的众数。保证众数出现次数超过一半。
摩尔投票法基于一个定理：在上述条件下，删去两个不同的数，众数的出现次数仍超过一半。
若众数原来的出现次数为 \(m\) ，这个定理其实就是 \(\dfrac mn>\dfrac12 \Rightarrow \dfrac{m-1}{n-2}>\dfrac12\) ，数学上显然正确
换种方式来说，我们从中不断任选两个不同的数，相互抵消
发现最坏情况也就其它数联合起来和众数抵消，而众数出现次数超过一半，所以一定不会被全部消掉
消到剩下所有数都只有同一个值时，就一定是众数
具体实现是这样的：
设 \(t\) 表示当前数的值，\(cnt\) 表示出现次数。\(cnt=0\) 时 \(t\) 随便取值，反正没意义
然后我们读进来一个数 \(x\)
如果 \(cnt=0\) ，记下当前数 t=x,++cnt;
如果 \(cnt>0,t\ne x\) ，抵消 --cnt;
如果 \(cnt>0,t=x\) 就 ++cnt;
最后 \(t\) 的值就是众数。
一个简单的拓展
仍然是找众数，但仅保证众数出现频率超过 \(\dfrac13\) 。
这时仍然有一条定理：删去三个互不相同的数，众数出现频率仍超过 \(\dfrac13\)
对应的代码实现只需维护两个不同的数值及其出现次数。
最后还要扫一遍原数组算出两个数的出现次数，取符合条件者
进一步可推广至出现频率超过 \(\dfrac1k\)
时间复杂度是 \(O(nk)\) 的，\(k\) 很小时也许有用，否则跑不过 sort
一个思想挺类似的构造题
给定一张 \(n\) 个点 \(m\) 条边的图，\(n\) 是 \(3\) 的倍数，保证存在一个大小为 \(\frac23n\) 的团（每两点间都有边），要求输出一个大小为 \(\frac13n\) 的团。
每次找到两个没有直接连边的点，将它们一起删去。\(\frac13n\) 次操作后，剩下的 \(\frac13n\) 个点即符合要求。