特殊情况求众数——摩尔投票法

题面

怕自己忘记这些奇技淫巧

给定一个长度为 \(n\) 的序列 \(A\)，要你求这个序列的众数，保证这个众数出现次数 \(>\lfloor\frac{n}{2}\rfloor\). 要求时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\).

设这个众数为 \(x\)，已经出现了 \(y\) 次，一开始 \(y=0\).

枚举从 \(1\) 到 \(n\)：

如果 \(y=0\)，直接令 \(x=A_i,y=1\)，\(x\) 就是 \(A[1..i]\) 的众数。

如果 \(y>0\)，

  如果 \(x=A_i\)，显然 \(y\) 加一；

  否则，\(y\) 减去一。当这个 \(y\) 减到 \(0\) 的时候，就说明 \(x\) 和非 \(x\) 元素个数相等，这个时候会重新挑选众数。最后的 \(x\) 就是答案。

《奇怪的算法增加了》

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;
int n,a,ans,cnt;
int main(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d",&a);
		if(!cnt){
			ans=a;
			cnt=1;
		}else{
			if(ans==a)cnt++;
			else cnt--;
		}
	}
	printf("%d",ans);
	return 0;
}