绝对众数/摩尔投票法

摩尔投票求绝对众数，使用 $ans$ 记录当前众数，$cnt$ 记录 $ans$ 的票数，当 $cnt=0$ 时说明未找到众数。每次处理序列第 $i$ 个数字 $a_i$。$cnt=0$ 时令 $ans=a_i,cnt=1$；$ans \neq a_i$ 时令 $cnt=cnt-1$；$ans=a_i$ 时令 $cnt=cnt+1$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

#include<bits/stdc++.h>
using namespace std;
int n,ans,sum;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        static int x;
        scanf("%d",&x);
        if(sum==0) sum=1,ans=x;
        else ans==x ? sum++:sum--;
    }
    printf("%d\n",ans);
    return 0;
}