自动搬运

查看原文

来自洛谷，原作者为

	hezhiran 这个家伙很不懒，什么都留下了||愿天堂暴力终能干翻正解ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็

搬运于2025-08-24 21:18:17，当前版本为作者最后更新于2025-04-02 20:49:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

有 $N$ 个数，求其中出现次数超过一半（ $\frac{N}{2}$ 的结果向下取整）的那个数。

思路

用一个 map 来存储每一个数的出现次数，再循环遍历每一个出现次数超过一半的。

可是这样交上去会超时，于是我们可以把判断的代码放到输入的循环中，如果满足条件直接输出并 return。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000010];
map<int,int> mp;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int ans=-1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]++;
		if(mp[a[i]]>n/2){
			ans=a[i];
			cout<<ans;
			return 0;
		}
	}
	cout<<"No\n"; 
	return 0;
}