c++算法，关于出现频率最大的数的问题

2024-11-28 13:33:38

推荐回答（2个）

回答1：

如果使用hashmap，则复杂度应该是o(n+n*logm+m)，m为字符串的种数,m<=n。理解为对遍历数组O(n)+对hashmap的检索和对象添加O(n*logm)+对hashmap进行遍历查找最大值。

以下方法可以做一点点优化。复杂度应该是o(n+n*logn）,即一次遍历和一次快速排序
1、将原字符串数组排序（让同一字符串排在一起）
2、设置一个变量用于存放当前最大值
3、遍历一次数组，记录同个字符串出现的次数，当次数大于最大值时，更新最大值

a[n];
对a[n]进行排序;
int max=0;int num=1;
string b=a[0];
for(int i=1;iif(b!=a[i]){
if(max max=num;
}
b=a[i]
num=1;
}else{
num++;
}
}

回答2：

这种问题，必然是O（n）级别的，没必要追求更快了。