https://www.luogu.com.cn/problem/T324159

题目大意：

给定一个大小为 $n$ 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 $\lfloor \frac{n}{2} \rfloor$ 的元素。
并且给定的数组总是存在多数元素。

我们现在希望使用时间复杂度 $ O(n) $ ，空间复杂度 $O(1)$ 的算法求解（此处的空间复杂度 $O(1)$ 代表不允许使用数组)

输入格式

第一行两个数 $n$

表示有 $n$ 个数

接下来 $n$ 行每行1个数 $ a_i $

输出格式

第一行一个数 $x$

样例

输入

3
3 2 3

输出

说明

$\cdot$ 对于 $100\%$ 的数据，$n \le 10^{5}$，$a_i \le 10^{9}$。(悲，洛谷的数据传不上 $100$ 个 $ 10^{7}$ ，所以就降下来了，不过时间可以再卡到 $ 50 \text{ms} $

题解

Boyer-Moore 投票算法。

#include<bits/stdc++.h>
#define for1(i,a,b) for(register int i = a;i <= b;i ++)
using namespace std;
int num,now,n,x;
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); 
	cin >> n;
	for1(i,1,n) 
	{
		cin >> x;
		now = (num == 0?x:now);
		num += (x == now?1:-1);
	}
	cout << now << '\n';
	return 0;
}