[bzoj2456]mode 题解
2024-09-05 22:12:02
改题改自闭的时候当然要靠水题来调节心情(逃
2456: mode
Time Limit: 1 Sec Memory Limit: 1 MB
Submit: 8461 Solved: 3171
[Submit][Status][Discuss]
Description
给你一个n个数的数列,其中某个数出现了超过n div 2次即众数,请你找出那个数。
Input
第1行一个正整数n。
第2行n个正整数用空格隔开。
Output
一行一个正整数表示那个众数。
Sample Input
5
3 2 3 1 3
3 2 3 1 3
Sample Output
3
HINT
100%的数据,n<=500000,数列中每个数<=maxlongint。
裸的摩尔投票法。
$1MB$的内存显然不能开任何数组。维护两个变量$id,cnt$。当$cnt$为0时,令当前输入的数为$id$,然后把$cnt$置为1。否则,如果当前输入与$id$相等则$cnt++$,反之$cnt--$。
因为只需要求出现次数大于$\frac{n}{2}$的数,所以只维护当前有可能成为答案的数,如果出现了别的数相当与抵消了一次这个数的贡献,出现了这个数那么贡献+1。
#include<cstdio>
int n,x,id,cnt;
void add(int x)
{
if(!cnt)id=x,cnt=1;
else
{
if(id==x)cnt++;
else cnt--;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
add(x);
}
printf("%d\n",id);
return 0;
}
最新文章
- Linux 双网卡绑定
- 【C#进阶系列】22 CLR寄宿和AppDomain
- BES
- Openvswitch原理与代码分析(3): openvswitch内核模块的加载
- dd 生成指定大小文件
- 爱莲(iLinkIT)的架构与原理
- 暑假集训(1)第八弹 -----简单迷宫(Poj3984)
- 创建springbootdemo后运行报MongoSocketOpenException错误解决方法
- Icon font font face
- malloc,calloc,realloc,alloc
- .NET: 谈谈C#中的扩展方法
- 关于EF的三种分类----CodeFirst
- 优化实现Mobile/Bumped Diffuse
- SQL Server 限定删除一行
- :适配器模式:Adapter
- windows 环境下如何使用virtualenv python环境管理工具
- [转]Mahout推荐算法API详解
- 日期选择器(DatePicker)
- 定时登录下载sftp服务器上的某些有规则的文件
- SpringMVC初写(二)映射类型、限制和数据绑定