日期:2014-05-20  浏览次数:20699 次

一道纠结有熟悉的笔试题
有一亿个电话号码,其中可以有相同的号码。请编写算法实现每个号码出现的次数。

------解决方案--------------------
分治 一亿个号码用哈希函数映射到不同的文件然后小文件里统计号码出现次数
------解决方案--------------------
根本不要想,靠你的就是bitmap算法。
------解决方案--------------------
Bitmap可以统计次数么?假设一亿个号码全部是同一个那不能用一个bit来表示吧~希望我的理解没有错误
探讨

根本不要想,靠你的就是bitmap算法。

------解决方案--------------------
探讨
Bitmap可以统计次数么?假设一亿个号码全部是同一个那不能用一个bit来表示吧~希望我的理解没有错误

引用:

根本不要想,靠你的就是bitmap算法。

------解决方案--------------------
是啊 但是如果不知道最大相同元素有几个 不好确定表示每个元素应该用几个bit啊
探讨

引用:
Bitmap可以统计次数么?假设一亿个号码全部是同一个那不能用一个bit来表示吧~希望我的理解没有错误

引用:

根本不要想,靠你的就是bitmap算法。

bitmap并非一定每个元素是 bit。。。

------解决方案--------------------
探讨
是啊 但是如果不知道最大相同元素有几个 不好确定表示每个元素应该用几个bit啊

引用:

引用:
Bitmap可以统计次数么?假设一亿个号码全部是同一个那不能用一个bit来表示吧~希望我的理解没有错误

引用:

根本不要想,靠你的就是bitmap算法。

bitmap并非一定每个元素是 bit。。。

------解决方案--------------------
好吧,我看错了。

电话号码不能是整数,因为8位乃至11位根本装不下。

而且它应该非常稀疏。

用trie tree
------解决方案--------------------
说说思路吧:
第一步:首先用hash并求模,将文件分解为多个小文件,对于单个文件利用第二步的方法求出每个文件件中号码的次数。比如模1000,把整个大文件映射为1000个小文件,然后再进行归并处理,得到每个号码出现的次数。
第二步,先统计次数: 
维护一个Key为电话号码,Value为该号码出现次数的HashTable,每次读取一个号码,如果该号码不在Table中,那么加入该字串,并且将Value值设为1;如果该号码在Table中,那么将该号码的计数加一即可。