作用:用$O(n)$的时间求出一个数组中出现次数严格超过一半的数字

证明:

设数组长度为n,且n为奇数,如果存在两个多数元素,x是多数元素,且数量为a,y是另一个多数元素数量为b,根据定义,a和b都大于n/2,与假设矛盾,因此原命题成立

代码讲解:

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt=0,id=0; //cnt记录当前出现次数最多的那个数的出现次数,id记录当前出现次数最多的那个数
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x==id) cnt++; //当前数与出现次数最多的数相同,cnt++;
        else{
            if(cnt) cnt--; //每次让当前这个数与目前出现次数最多的那个数(id)对掉一个
            else{ //当前这个数的出现次数已经小于不等于他的数的出现次数,更改当前出现次数最多的数
                cnt=1; //当前有x这一个数
                id=x;
            }
        }
    }
    cout<<id<<endl;
    return 0;
}