摩尔投票

\(n\) 个人投票,保证存在绝对众数,问你最后谁的票最多?

1.暴力

开个数组扫一遍或者排序,\(n/2\) 的位置必定为答案.

2.摩尔投票

看作每个票可以互相抵消.假设当前存在一个答案 \(k\) ,如果让 \(k=a_i\) 那么 \(k\) 抵消的次数加一,否则 \(k\) 的抵消次数减少一.如果 \(k\) 的抵消次数为 \(0\) ,让 \(a_{i+1}\) 成为新的 \(k\) .如果不存在绝对众数,只保证存在众数,那么需要再花时间扫描一般来判断.
算法时间复杂度 \(O(n)\) ,空间复杂度 \(O(1)\) .

Code

#include<bits/stdc++.h>
using namespace std; 
int n,m,count1,more;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		if(count1==0) more=m,count1++;
		else if(more==m) count1++;
		else count1--;
	}
	cout<<more;
	return 0;
} 

3.更快的方法

如果空间够用,那么用一个桶,如果 \(a_i\) 出现的次数 \(\geq n/2\) 那么这个数立刻当选.