统计一个字符串中重复最多的字符及重复的次数

modestyang

我是用二重循环来做的。
for(i=0; i<n; i++)
    for(j=0; j<n; j++)
          if(a==a[j])   count++;

if (count>max)  record;
return record;

但是感觉这样时间复杂度蛮高的。
请教有什么更好的方法吗?

ivhb

short x[0xFF];

x[s[0]] ++;

ljok30

要想提高效率,必须从外层循环考虑:提供两个思路
1,把字符串中所有可能出现的字符作为循环的依据.这样在字符串的字符个数远大于这个集合的个数时,效率会提高不少.
2,把字符串转换成存储结构,设置访问标示,这样不但可以减少外层循环,还可以减少内层循环,效率也应该能提高不少!

cjaizss

先排序，再遍历一遍

aero

原帖由 ivhb 于 2007-11-5 09:35 发表
short x[0xFF];

x[s[0]] ++;

如果空间不限制，基本这个空间也没多少，ivhb的这个方法我觉得是最好的。时间复杂度只有n。

yecheng_110

原帖由 ivhb 于 2007-11-5 09:35 发表
short x[0xFF];

x[s[0]] ++;

当时一个面试题
这种方法时间复杂度为O(n)
因为是字符串空间也不多

cjaizss

先排序再统计，时间复杂度o(nlogn),空间复杂度o(1)（有些排序需要更高的空间复杂度）
遍历进行数组次数累计，时间复杂度o(n),空间复杂度o(1)（字母集合的势）

[ 本帖最后由 cjaizss 于 2007-11-5 13:46 编辑 ]

cjaizss

但是，有一点必须要说，只遍历一遍分别累计次数，属于非通用算法

cugb_cat

原帖由 cjaizss 于 2007-11-5 13:45 发表
但是，有一点必须要说，只遍历一遍分别累计次数，属于非通用算法

acm的好多题目的题解都是这么干的，特变态。

jigloo

怎么就不是通用算法？这个分明就是用hash的思想。