找出字符串出现次数最多的字符
这是去哪儿网的面试题。问题：
给定一个字符串，要求把字符串中出现次数最多的字符打印出来。
分析：
不置可否，肯定要统计每个字符出现的次数，然后根据字符出现次数的大小打印出出现次数最多的字符，另外需要注意的是出现次数最多的字符个数可能不止一个。
解决方案：
1 最容易想到的就是建立一个map，字符作为key，初始化次数cnt为0，每次遍历数组中的一个元素的时候，如果能在map中查到该字符，那么该map元素的cnt++，如果没有找到该元素，那么在map中插入该元素，并且cnt++。这样的话遍历完整个数组的时间复杂度是O(n*logn)。
然后再遍历整个map找到元素最大的，总之这个方法效率不是很高
2 利用哈希表的思想 或者说是计数排序的思想，ASCII码中字符的个数不超过256，我们就创建一个大小为256的数组，然后遍历数组，直接将字符对应的ASCII码作为数组的索引，索引对应的计数次数+1.这样统计每个字符出现的次数的时间复杂度就是是O(n)了。
然后的就简单了，遍历计数数组，遇到跟当前出现次数一样大的就压栈，如果遇到更大的就把之前的出栈，再把当前最大的压栈，如此即可。
3 程序实现：#include <iostream>
#include <vector>
using namespace std;
void findMaxChar(char* str);
void main()
{
char* str = "I'm a good boy!!!";
findMaxChar(str);
}
void findMaxChar(char* str)
{
int strn = {0};
char *p = str;
while(*p != '\0')
{
strn[*p]++;
p++;
}
vector<char> vec;
int nMax=-1;
for(int i=0;i<256;i++)
{
if(strn==nMax)
vec.push_back(i);
if(strn>nMax)
{
while(!vec.empty())
vec.pop_back();
vec.push_back(i);
nMax = strn;
}
}
vector<char>::iterator iter;
for(iter=vec.begin();iter<vec.end();iter++)
cout<<*iter<<endl;
}
页:
[1]