07.摩尔投票
摩尔投票
是一种用来解决 绝对众数
问题的算法。
在一个集合中,如果一个元素的出现次数比其他所有元素的出现次数之和还多,那么就称它为这个集合的 绝对众数
。等价地说, 绝对众数
的出现次数大于总元素数的一半。
摩尔投票
的过程非常简单,让我们把找到绝对众数的过程想象成一次选举。我们维护一个 m
,表示当前的候选人,然后维护一个 cnt
。对于每一张新的选票,如果它投给了当前的候选人,就把 cnt
加1,否则就把 cnt
减1(也许你可以想象成,B的一个狂热支持者去把A的一个支持者揍了一顿,然后两个人都没法投票)。特别地,计票时如果 cnt == 0
,我们可以认为目前谁都没有优势,所以新的选票投给谁,谁就成为新的候选人。
如果我们要求的是
众数
,这样的做法并不能给出正确答案,但如果要求的是绝对众数
(且绝对众数确实存在),那么m
一定是正确的。
Last updated