腾讯面试题：有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。

有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。
请用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 int
struct 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)


csdn

有空研究一下用 python实现一下

应该可以用MATLAB处理的

不懂C++。。。只会Java.楼主有java的实现吗？
还有，如果只用MapReduce来实现的话，运行两个Job也可以，但是会比楼主的办法麻烦很多，学习了~

hochikong 发表于 2014-4-7 11:18
有空研究一下用 python实现一下

哈哈，随便用的头像

额 记得之前也遇到过这个不过越到的是说10亿条

学习学习,那不错的