一、题意前提 给定 个投票编号，保证存在唯一一个编号，票数严格超过总票数一半。
设该编号得票数为 ，满足： 小于n
二、核心思想 不一样的数互相抵消，最后剩下的候选人，就是绝对多数。
三、维护变量 ：当前候选代表 ：候选存活计数器 四、算法规则 若 ： 更换当前数为新候选，令 当前数， 当前数与候选 相同： 自己人， 当前数与候选 不同： 相互抵消， 遍历一遍所有数，最终 就是答案。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int candidate=0,cnt=0;
int x;
for (int i = 0; i < n; i++)
{
cin>>x;
if (cnt==0)
{
candidate=x;
cnt=1;
}
else if (x==candidate)
{
cnt++;
}
else
{
cnt--;
}
}
cout<<candidate<<'\n';
return 0;
}
小心O(n)
暂无评论