主元素问题

参考资料

• 主元素问题 - OI Wiki

例题

洛谷 P2397 yyy loves Maths VI (mode)

洛谷 P2397 yyy loves Maths VI (mode)

一共有 $n$ 个正整数 $a_i$，他让 redbag 找众数。他还特意表示，这个众数出现次数超过了一半。

代码（1）

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	int now,cnt=0;
	while(n--)
	{
		int x;
		cin>>x;
		if(!cnt)now=x;
		if(now==x)cnt++;
		else cnt--;
	}
	cout<<now<<'\n';
	return 0;
}