现在的位置: 首页 > 综合 > 正文

算法题41 超大数据量遍历查找

2013年06月17日 ⁄ 综合 ⁄ 共 504字 ⁄ 字号 评论关闭

1、一个文件,内含一千万行字符串,每个字符串在1K以内,要求找出所有相反的串对,如abc和cba

 

 


2、有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。请用5分钟时间,找出重复出现最多的前10条。

 

算法:建一个红黑树,比如STL中的map1,key为短信的hash值如MD5值,value为该短信出现的次数。

同时维护一个另一个只有10个节点的map2,key为短信的hash值如MD5值,value为该短信出现次数和短信。

建一个临时变量temp,存放当前前十个出现次数最多的短信中次数最小的那个的md5值。

 

每遍历一行短信,生成其MD5值,

如果map1中没有该key插入新节点,key为MD5值,value为1;如果map2的size小于目标个数,插入新节点,key为1。

否则就是已经出现在map1中,其key+1,判断当前短信是否在map2中),如果在key+1,如果不在,比较当前key与map2[temp]的大小,如果小于等于什么也不做,如果大于更新map2替换map2[temp],并更新temp.直至遍历一遍结束。最多的前十条就在map2里。

 

这样只需访问一遍文件且节省内存空间。

 

抱歉!评论已关闭.