题目Description
给你一个n个数的数列，，其中某个数出现了超过n div 2次即众数，请你找出那个数。
Input
第1行一个正整数n。 第2行n个正整数用空格隔开。
Output
一行一个正整数表示那个众数。
Sample Input
5 3 2 3 1 3
Sample Output
3
HINT
100%的数据，n<=500000，数列中每个数<=maxlongint。
代码MLE的map= =
本来还以为用个map可以划划水过了
1M内存= =数据应该是专门卡map的
;ll;int n,ans,t,mxcnt=0;map<int,int>m;int read(){int x=0,f=1;char ch=getchar();while(ch<‘0’||ch>’9′){if(ch==’-‘)f=-1;ch=getchar();}while(ch>=’0’&&ch<=’9’){x=x*10+ch-‘0’;ch=getchar();}return x*f;}int main(){n=read();R0(i,n){t=read(),m[t]++;if(mxcnt<m[t])mxcnt=m[t],ans=t;}printf(“%d”,ans);return 0;}O（n）求众数
原=>kivienst
众数性质 【性质一】如果一个数在某区间内出现的次数大于区间长度的一半，则这个数一定是该区间的第(r – l + 1) >> 1 大 –>可以用划分树求区间第k大 【性质二】如果一个数在某区间内出现的次数大于区间长度的一半，则这个数的每个二进制位在该区间内出现的次数也一定大于区间长度的一半！！！所以就可以直接确定出那个数！！！！！ 【性质三】对两两不相等的数进行抵消，则最后剩下的数则是该众数！！！ 用num记录当前抵消后剩下的数，当num=0的时候把该数变为tmp，不等则cnt–,相等则cnt++
n, num;int main(){scanf(“%d%d”, &n, &num);int cnt = 1;for (int i = 2; i <= n; i++){int tmp; scanf(“%d”, &tmp);if (cnt == 0){cnt = 1;num = tmp;continue;}if (tmp == num) cnt++;else cnt–;}printf(“%d\n”, num);return 0;}
既有美妙的风景，也会有称不上景、只有风的地方。
