A41013. 众数问题
填空题
中等
知识点
题目描述
众数问题
题目描述
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。
编程任务：
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。
输入格式
第1行多重集S中元素个数n(n<=50000)；接下来的n 行中，每行有一个自然数。
输出格式
输出文件有2 行，第1 行给出众数，第2 行是重数。(如果有多个众数，只输出最小的)
样例输入
6
1
2
2
2
3
5
样例输出
2
3
参考答案
#include<stdio.h>
#define N 50001
typedef struct SNum{
int s; //元素的值
int t; //元素在多重集合中出现的次数
}Num;
Num S[N];
int main(){
int n,s,i,v,m=0,c=0;
scanf("%d",&n);
while(n--){ //n行中
scanf("%d",&s); //每行一个自然数
for(i=0;i<c;i++){ //寻找集合S
if(s==S[i].s){ //若s在集合S中出现过
S[i].t++; //出现的次数加1
if(S[i].t>m) //若出现次数最多
m=S[i].t; //更新众数的重数
break;
}
}
if(i==c){ //若s在集合S中还未出现过
S[c].s=s; //将s添加到S中
S[c].t=1; //出现了1次
c++; //集合S中有c个元素
}
}
v=0x7fffffff;
for(i=0;i<c;i++){ //在集合S中寻找
if(S[i].t==m&&S[i].s<v) //最小的众数
v=S[i].s;
}
printf("%d\n%d\n",v,m);
return 0;
}
上一题
下一题