摩尔投票

摩尔投票是一种用来解决绝对众数问题的算法。

在一个集合中，如果一个元素的出现次数比其他所有元素的出现次数之和还多，那么就称它为这个集合的绝对众数。等价地说，绝对众数的出现次数大于总元素数的一半。

摩尔投票的过程非常简单，让我们把找到绝对众数的过程想象成一次选举。我们维护一个m ，表示当前的候选人，然后维护一个 cnt。对于每一张新的选票，如果它投给了当前的候选人，就把 cnt 加1，否则就把 cnt 减1。特别地，计票时如果 cnt=0 ，我们可以认为目前谁都没有优势，所以新的选票投给谁，谁就成为新的候选人。

例如，5张选票分别投给1，3，3，2，3，则：

轮数	1	2	3	4	5
m	1	1	3	3	3
cnt	1	0	1	0	1

这个过程可以转换成C++代码（设总人数为 n）：

int m = 0, cnt = 0;
for (int i = 0; i < n; ++i)
{
    if (cnt == 0)
        m = A[i];
    if (m == A[i])
        cnt++;
    else
        cnt--;
}
// 最后需要验证答案是否符合要求

如果我们要求的是众数，这样的做法并不能给出正确答案，但如果要求的是绝对众数（且绝对众数确实存在），那么 m 一定是正确的.

这是因为，在最后计票时，我们知道有 cnt 张票投给了 m ，假如绝对众数另有其人，那么一定是剩下的票投出来的。但剩下的 n-cnt 张票都是在“捉对厮杀”的过程中被抵消掉的，每一对被抵消的票都来自不同的候选人，所以一个候选人最多在这里拿到\(\frac{n-cnt}{2}\) 票，这不可能大于 n/2 。但绝对众数确实存在，所以这个绝对众数就一定是 m 。

如果绝对众数不存在，摩尔投票会给出一个错误的解，所以一定要记得验证答案。

这个算法是 O(n) 时间复杂度、 O(1) 空间复杂度的。

核心就是对拼消耗。

玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。