BZOJ 2456: mode(新生必做的水题)

2456: mode

Time Limit: 1 Sec  Memory Limit: 1 MB Submit: 4868  Solved: 2039

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。

zju2132 The Most Frequent Number

Source

鸣谢 黄祎程

题目链接: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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

BZOJ 3211: 花神游历各国【线段树区间开方问题】

3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 3514  Solved: 1306...

3225
来自专栏算法修养

URAL 2040 Palindromes and Super Abilities 2(回文树)

Palindromes and Super Abilities 2 Time Limit: 1MS Memory Limit: 102400KB ...

3584
来自专栏ml

HDUOJ 2672---god is a girl 《斐波那契数》

god is a girl Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

2806
来自专栏ml

HDUOJ----剪花布条

剪花布条 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

35612
来自专栏码匠的流水账

聊聊flink的SourceFunction

flink-streaming-java_2.11-1.6.2-sources.jar!/org/apache/flink/streaming/api/func...

2303
来自专栏HansBug's Lab

2301: [HAOI2011]Problem b

2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 1737...

2575
来自专栏小樱的经验随笔

BZOJ 1012: [JSOI2008]最大数maxnumber【线段树单点更新求最值,单调队列,多解】

1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 103...

2966
来自专栏数据结构与算法

BZOJ4269: 再见Xor(线性基)

给定N个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。

674
来自专栏算法修养

HYSBZ 3676 回文串 (回文树)

3676: [Apio2014]回文串 Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 1680  Solve...

3487
来自专栏ml

HDU----(3294)Girls' research(manacher)

Girls' research Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3...

2805

扫码关注云+社区

领取腾讯云代金券