算法1

(摩尔投票)

C++ 代码

#include<iostream>
using namespace std;
const int N=1100;
int a[N];
int main(){
    int n;
    cin>>n;
    int cnt=0,val;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) {
        if(!cnt) val=a[i],cnt++;
        else if(a[i]==val) cnt++;
        else cnt--;
    }
    cnt=0;
    for(int i=0;i<n;i++)
        if(a[i]==val) cnt++;
    if(cnt<=n/2) puts("no") ;
    else cout<<val<<endl;
    return 0;
}

算法2

(hash表)

C++ 代码

#include<iostream>
#include<unordered_map>
using namespace std;
const int N=1100;
int a[N];
unordered_map<int,int> cnt;
int main(){
    int n;
    cin>>n;
    int flag=0;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) {
           cnt[a[i]]++;
           if(cnt[a[i]]>n/2)  {
               cout<<a[i];
               flag=1;
               return 0;
           }
    }
    if(!flag) puts("no");
    return 0;
}