最多的100个IP

我们现在有一份用户登录IM的IP记录文件,每一行是一个IP,文件大小10G,我们怎么能快速的找到出现次数最多的100个IP呢?要求使用的内存不超过1G。
这题怎么破????
全部评论
两次遍历即可,第一遍分批把ip读入内存,hash 到100个桶里面,平均每个桶100m,所以相同的IP会被hash到同一个桶里,第二遍分别读一个桶进内存,统计top100IP即可
点赞 回复 分享
发布于 2017-09-13 09:27
1. 将文件分割成10个子文件,这样每个文件都可以读入内存进行排序。 2. 对每个子文件取top100(采用小顶堆,首先取前100个构建小顶堆,然后依次与堆顶比较,如果大于堆顶,则替换堆顶,并调整小顶堆,遍历到最后,得到top100),然后将每个子文件的top100进行归并排序,求出最终的top100.
点赞 回复 分享
发布于 2017-09-13 09:32
trie树
点赞 回复 分享
发布于 2017-09-13 10:53
这题在我秋招面试笔试出现了4次👀
点赞 回复 分享
发布于 2017-09-13 09:41
从文件中读取,哈希每一个ip,将哈希值一样的存到同一个文件中。 然后再从每一个文件中读取,这时用map记录一下每个ip出现的次数,一个文件可以得到一个出现在该文件中次数最多的ip,最后得到文件数量个ip,然后比较这些ip出现的次数,就可以得到结果。这个思路应该可行,如果不对请求指正
点赞 回复 分享
发布于 2017-09-13 09:34

相关推荐

05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务