Time Limit: 1 Sec Memory Limit: 1 MB Submit: 4868 Solved: 2039
给你一个n个数的数列,其中某个数出现了超过n div 2次即众数,请你找出那个数。
第1行一个正整数n。 第2行n个正整数用空格隔开。
一行一个正整数表示那个众数。
5 3 2 3 1 3
3
100%的数据,n<=500000,数列中每个数<=maxlongint。
zju2132 The Most Frequent Number
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2456
分析:此题极其诡异,先看内存,1MB,这一点估计就会卡到死吧,然后就是显然不能开数组做,说水题其实也不是很水,怎么做,下面给出一种非常神奇的做法!
题目里定义的众数出现次数超过数组的一半 其他所有数加起来都没它多! 那就我定义一个cnt=1(至少要一个数)和res=0(初始化) 如果下一个数不等于res就抵消掉让cnt-1;当cnt为0时把res赋成下一个数 最后结果就是res,因为剩下没有数能够抵消它!
下面给出C语言AC代码:(尽量别去跑C++,耗时耗内存)
1 #include <stdio.h>
2 int main()
3 {
4 int n;
5 scanf("%d",&n);
6 int res=0,cnt=1,c;
7 for(int i=1;i<=n;i++)
8 {
9 scanf("%d",&c);
10 if(c==res)
11 cnt++;
12 else cnt--;
13 if(cnt<=0)
14 {
15 res=c;
16 cnt=1;
17 }
18 }
19 printf("%d",res);
20 return 0;
21 }