开发者社区 问答 正文

[@徐雷frank][¥20]我现在有一亿个正整数,平均存储在100个文本里面,每行一个数字; 每个文件里面数字的顺序是随机的,给定一个数字,如果快速确定它在特定文件的哪一行?

我现在有一亿个正整数,平均存储在100个文本里面,每行一个数字; 每个文件里面数字的顺序是随机的,给定一个数字,如果快速确定它在特定文件的哪一行?

展开
收起
晓生寒 2018-12-14 15:20:22 2473 分享 版权
1 条回答
写回答
取消 提交回答
  • 1.阿里云大学荣誉讲师, 2.MongoDB中文社区专家

    1、这个算法问题,我给个思路,可以一起讨论最优算法。1亿个数字,100个文件,并且文件中的数字是无序的。
    2、要快速定位任意一个数字所在的文件和行号。我们可以参考B树算法。
    3、构建一颗B树,Node节点定义,包括左右指针,key也就是数字,以及保存文件File和行号lineNum值(链表,同一个数出现的不同文件的不同行)。
    4、构建出来的B树,假设极端情况,数字都不一样,构建的B树,高度分叉N,N=2的时候,1亿个数字,高度应该是30。logN取顶。
    5、当搜索某个数字的时候,匹配算法最坏是遍历到底,LogN整数次+链表长度M,基本是O(N)有限常数次找到或者找不到。
    6、假设不考虑内存,还有一个算法,直接使用Hashtable,每个数字作为key,文件编号和行号作为value保存。,这个复杂度是O(1)。最坏情况取决于重复链表长度,不过Java1.8以后红黑树也可以使用LogM,查找次数更少。

    2019-07-17 23:21:00
    赞同 展开评论
问答分类:
问答地址: