AcWing 3192. 出现次数最多的数
原题链接
简单
作者:
tobequiet
,
2025-02-04 23:31:52
,
所有人可见
,
阅读 2
考点:统计众数
思路:
用哈希表统计每个数字出现的次数。
用 tmp 表示数字,cnt 表示 tmp 出现的次数。初始状态:tmp = 0, cnt = 0;
遍历哈希表,如果遍历到的数字出现的次数大于 tmp ,或者遍历到数字小于 tmp 且出现次数等于 cnt,更新 tmp 和 cnt 为当前组合。
输出 cnt 即为答案。
哈希表求众数 求出现最多的数
借助count[],一个存哈希值,一个存对应哈希编码里面的出现个数,构造映射
相当于手写unordered_map<int,int> 一个对应哈希值,一个对应的出现数量,也相当于是构造映射
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const N = 2003, null = 0x3f3f3f3f;
int n;
int h[N],count[N];
int find(int x){
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x){
k++;
if(k == N){
k = 0;
}
}
return k;
}
int main(){
scanf("%d",&n);
memset(h,0x3f,sizeof h);
while(n--){
int x;
scanf("%d",&x);
int k = find(x);
count[k] ++;
h[k] = x;
}
int cnt = 0;//次数
int tmp = 0;
for(int i = 0; i < N ;i++){
if(count[i] > cnt || count[i] == cnt && h[i] < tmp){
tmp = h[i];
cnt = count[i];
}
}
printf("%d\n",tmp);
return 0;
}