发布于 2014-10-27 07:44:54 | 163 次阅读 | 评论: 0 | 来源: 网友投递
去哪儿网
去哪儿网（Qunar.com）总部位于北京，于2005年5月,由庄辰超与戴福瑞(Fritz Demopoulos)、道格拉斯(Douglas Khoo)共同创立。作为中国第一个旅游搜索引擎，使中国旅行者首次能够在线比较国内航班和酒店的价格及服务。
本文是一道去哪儿网的面试题:找出字符串出现最多的字符 ，有参考答案，感兴趣的同学参考下。
面试问题：
给定一个字符串，要求把字符串中出现次数最多的字符打印出来。
分析：
不置可否，肯定要统计每个字符出现的次数，然后根据字符出现次数的大小打印出出现次数最多的字符，另外需要注意的是出现次数最多的字符个数可能不止一个。
解决方案：
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[256] = {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[i]==nMax)
vec.push_back(i);
if(strn[i]>nMax)
{
while(!vec.empty())
vec.pop_back();
vec.push_back(i);
nMax = strn[i];
}
}
vector<char>::iterator iter;
for(iter=vec.begin();iter<vec.end();iter++)
cout<<*iter<<endl;
}