[@徐雷frank][¥20]我现在有一亿个正整数，平均存储在100个文本里面，每行一个数字； 每个文件里面数字的顺序是随机的，给定一个数字，如果快速确定它在特定文件的哪一行？
我现在有一亿个正整数，平均存储在100个文本里面，每行一个数字； 每个文件里面数字的顺序是随机的，给定一个数字，如果快速确定它在特定文件的哪一行？
展开
收起
1
条回答
写回答
写回答
-
1.阿里云大学讲师，主讲《微服务Spring Cloud设计与开发实战》《MongoDB高级实战》等课程 2.MongoDB中文社区专家 3.《MongoDB实战》第2版译者 5.吉林大学计算机科学学士、上海交通大学硕士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赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
