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

输出

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;
}