摩尔投票法(Boyer–Moore majority vote algorithm)

算法笔记2——摩尔投票法(Boyer–Moore majority vote algorithm)

1、简要概述

摩尔投票法(Boyer–Moore majority vote algorithm)出自论文，算法解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。常见的算法是扫描一遍选票，对每个候选人进行统计的选票进行统计。当候选人的数目固定时，这个常见算法的时间复杂度为：O(n)，当候选人的数目不定时，统计选票可能会执行较长时间，可能需运行O(n^2^)的时间。当选票有序时，可以很容易编出O(n)的程序，首先找到中位数，然后检查中位数的个数是否超过选票的一半。这篇论文针对无序且侯选人不定的情形，提出了摩尔投票算法。算法的比较次数最多是选票（记为n）的两倍，可以在O(n)时间内选出获票最多的，空间开销为O(1)

==摩尔投票法的一大应用就是求众数==。

2、算法步骤

算法分为两个阶段：pairing阶段和counting阶段。

• pairing阶段：两个不同选票的人进行对抗，并会同时击倒对方，当剩下的人都是同一阵营，相同选票时，结束。
• counting阶段：计数阶段，对最后剩下的下进行选票计算统计，判断选票是否超过总票数的一半，选票是否有效。

2.1 pairing阶段的简化

选票不同就要大干一架，太过粗鲁，这里提供一种更加现代化的文明方式。
在场的有个叫onwaier的，他很聪明，他想到一个方法。他用他那犀利人目光扫一遍所有代表们的选票，在脑子记住两件事，当前的候选人的名字cand和他对应的计数k（并不是他的选票数）。起始时，k的值为0，看每个人的选票时，先想想现在k是否为0，如果是0就将cand更新为他将看到的候选人的名字并且将k的值更新为1。观察每个人选票的过程，如果这个人的选票与cand相同，则将k的值加1；否则，将k的值减1。最后的cand可能胜选，还需统计他的总选票数是否超过一半。

2.2 证明

假设共有n个代表（一人一票，选票总数为n）。当onwaier看到第i个代表的选票时(1≤i≤n)，前面他已经看到的所有选票可以分为两组，第一组是k个代表赞同cand；另一组是选票可以全部成对（选票不同）抵销。当处理完所有的选票时，如果存在大多数，则cand当选。
假设存在一个x其不同于cand，但拥有的选票超过n/2。但因为第二组的选票可以全部成对抵销，所以x最多的选票数为(n-k)/2，因此x必须要收到第一组的选票才能超过一半，但是第一组的选票都是cand的，出现矛盾，假设不成立。
所以，如果存在大多数，cand就是那个。

3、算法代码

/*
根据多数元素出现的次数大于n/2且超过其它元素出现次数之和这一特点，进行统计
时间复杂度为：O(n)
空间复杂度为：O(1)
*/
int majorityElement(vector<int>& nums) {
	int k = 0, cand = 0;
	//成对抵销阶阶段
	for(auto num:nums){
		if(k == 0){
			cand = num;
			k = 1;
		}
		else{
			if(num == cand){
				++k;
			}
			else{
				--k;
			}
		}
	}
	//计数阶段 判断cand的个数是否超过一半
	k = 0;
	for(auto num:nums){
		if(num == cand){
			++k;
		}
	}
	if(k <= nums.size() / 2){
		cand = -1;//表示未超过一半 
	}
	return cand;
}