腾讯面试题解析：重复短信问题

腾讯面试题解析：重复短信问题2014-12-24有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。

有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。

请用5分钟时间，找出重复出现最多的前10条。

分析：

常规方法是先排序，在遍历一次，找出重复最多的前10条。但是排序的算法复杂度最低为nlgn。

可以设计一个hash_table, hash_map<string, int>，依次读取一千万条短信，加载到hash_table表中，并且统计重复的次数，与此同时维护一张最多10条的短信表。

这样遍历一次就能找出最多的前10条，算法复杂度为O（n）。

实现如下：

#include<iostream>#include<map>#include<iterator>#include<stdio.h>using namespace std;#define HASH __gnu_cxx#include<ext/hash_map>#define uint32_t unsigned int#define uint64_t unsigned long intstruct StrHash{uint64_t operator（）（const std::string& str） const{ uint32_t b= 378551; uint32_t a= 63689; uint64_t hash = 0; for（size_t i = 0; i < str.size（）; i++） {hash = hash * a + str[i];a= a * b; } return hash;}uint64_t operator（）（const std::string& str, uint32_t field） const{ uint32_t b= 378551; uint32_t a= 63689; uint64_t hash = 0; for（size_t i = 0; i < str.size（）; i++） {hash = hash * a + str[i];a= a * b; }hash = （hash<<8）+field; return hash;}};struct NameNum{string name;int num;NameNum（）:num（0）,name（""）{}};int main（）{HASH::hash_map< string, int, StrHash > names;HASH::hash_map< string, int, StrHash >::iterator it;NameNum namenum[10];string l = "";while（getline（cin, l））{it = names.find（l）;if（it ！= names.end（））{names[l] ++;}else{names[l] = 1;names[l] = 1;}}int i = 0;int max = 1;int min = 1;int minpos = 0;for（it = names.begin（）; it ！= names.end（）; ++ it）{if（i < 10）{namenum[i].name = it->first;namenum[i].num = it->second;if（it->second > max）max = it->second;else if（it->second < min）{min = it->second;minpos = i;}}else{if（it->second > min）{namenum[minpos].name = it->first;namenum[minpos].num = it->second;int k = 1;min = namenum[0].num;minpos = 0;while（k < 10）{if（namenum[k].num < min）{min = namenum[k].num;minpos = k;}k ++;}}}i++;}i = 0;cout << "maxlength （string,num）: " << endl;while（ i < 10）{cout << "（" << namenum[i].name.c_str（） << "," << namenum[i].num << "）" << endl;i++;}return 0;}

使用g++编译如下：

g++ main.cpp -o main

短信文本文件为：msg.txt

运行：./main < msg.txt

输出结果为：

maxlength （string,num）:
（点点母婴坊,4）
（农机配件维修,5）
（红胜超市,6）
（龙溪大酒店,8）
（张记饺子馆,3）
（友谊旅店,3）
（明珠通讯,3）
（金源旅馆,3）
（洞庭山天然泉水,2）
（清源超市,3）