# 07.摩尔投票

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

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

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

> 如果我们要求的是 `众数` ，这样的做法并不能给出正确答案，但如果要求的是 `绝对众数` （且绝对众数确实存在），那么 `m` 一定是正确的。
>
> [39.数组中出现次数超过一半的数字](https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/39.-shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi)
>
> [算法学习笔记(78): 摩尔投票](https://zhuanlan.zhihu.com/p/387744743)