找出字符串出现次数最多的字符

0x55AA

这是去哪儿网的面试题。
问题：
给定一个字符串，要求把字符串中出现次数最多的字符打印出来。
分析：
不置可否，肯定要统计每个字符出现的次数，然后根据字符出现次数的大小打印出出现次数最多的字符，另外需要注意的是出现次数最多的字符个数可能不止一个。
解决方案：
1 最容易想到的就是建立一个map，字符作为key，初始化次数cnt为0，每次遍历数组中的一个元素的时候，如果能在map中查到该字符，那么该map元素的cnt++，如果没有找到该元素，那么在map中插入该元素，并且cnt++。这样的话遍历完整个数组的时间复杂度是O(n*logn)。
然后再遍历整个map找到元素最大的，总之这个方法效率不是很高
2 利用哈希表的思想 或者说是计数排序的思想，ASCII码中字符的个数不超过256，我们就创建一个大小为256的数组，然后遍历数组，直接将字符对应的ASCII码作为数组的索引，索引对应的计数次数+1.这样统计每个字符出现的次数的时间复杂度就是是O(n)了。
然后的就简单了，遍历计数数组，遇到跟当前出现次数一样大的就压栈，如果遇到更大的就把之前的出栈，再把当前最大的压栈，如此即可。

3 程序实现：

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. void findMaxChar(char* str);
   
6. 
   
7. void main()
   
8. {
   
9.         char* str = "I'm a good boy!!!";
   
10.         findMaxChar(str);
    
11. }
    
12. 
    
13. 
    
14. 
    
15. void findMaxChar(char* str)
    
16. {
    
17.         int strn[256] = {0};
    
18.         char *p = str;
    
19.         while(*p != '\0')
    
20.         {
    
21.                 strn[*p]++;
    
22.                 p++;
    
23.         }
    
24.         vector<char> vec;
    
25.         int nMax=-1;
    
26.         for(int i=0;i<256;i++)
    
27.         {
    
28.                 if(strn[i]==nMax)
    
29.                         vec.push_back(i);
    
30.                 if(strn[i]>nMax)
    
31.                 {
    
32.                         while(!vec.empty())
    
33.                                 vec.pop_back();
    
34.                         vec.push_back(i);
    
35.                         nMax = strn[i];
    
36.                 }
    
37.         }
    
38. 
    
39.         vector<char>::iterator iter;
    
40.         for(iter=vec.begin();iter<vec.end();iter++)
    
41.                 cout<<*iter<<endl;
    
42. 
    
43. }

复制代码