题解：B4277 [蓝桥杯青少年组国赛 2023] 主要成分

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