关于“100g文件全是数组,取最大的100个数”解决方法汇总

原题如下:

有一个100G大小的文件里存的全是数字,并且每个数字见用逗号隔开。现在在这一大堆数字中找出100个最大的数出来。

我认为,首先要摸清考官的意图。是想问你os方面的知识,还是算法,或者数据结构。

如果是os: 无疑是外排序算法的选择。100g文件在当前的环境下是无法全部读入内存的。

如果是算法:我觉得这个题考虑排序就是错的,只需要比较。找出最大的即可。

无论是哪种,都不需要一个实际代码的解决方案。只提供思路就可以了。所以,这道题也可以从面试的角度去回答而不是技术层面回答。

至于在技术层面有没有必要研究这个问题,那就是个人有个人看法了。

比较机灵的回答:

继续询问考官:这100g的文件是不是已经排序好了的?

如果已排序,那还不是信手拈来?

比较极端的回答:

请问:
1,你使用的什么操作系统,100G的文件,NTFS的?vista还是win7的?内存有多少大?
2,如果里面的数字小于100个怎么办?
3,如果里面的第一个数字就是100G-198个字节,那么java是无法处理的,请给我一个可以处理的语言出来。
4,我知道你会说假设,但是,程序员的任务是解决实际问题,一切皆以实际问题出发。任何一个理论都是有实际模型的。
5,不知道是谁命的题,我建议他命题严谨点,我不希望有这样的同事或者上级,更不希望将来贵公司因为这样的人毁了前途。

(引用http://topic.csdn.net/u/20091013/10/d5d371dc-6dec-4034-bf31-432a47ffce96.html 22楼 downice)

关于比较数据思路新颖的回答:

如果全都是正整数的话,可以先比较长度,挑出长度最长的一类,然后再排序挑出前100,如果最长的一类不足100个,就在长度-1的一类里选...........

(引用http://topic.csdn.net/u/20091013/10/d5d371dc-6dec-4034-bf31-432a47ffce96.html 3楼 ZX_ARES

个人比较喜欢的回答:

我把这个算法分为两个阶段。这个是基于概率统计的算法。用统计的方法
有时比专家系统还有效,这是从开复老师的书《世界因你不同》里学到的。

第一,先期学习阶段:

先读入文件中前10万个数(具体多少视情况定),找出其中最大的100个数,
保存在一个数组MaxAry[100]里.(指针链表)

第二,正式查找阶段:

读入文件中一个数,并与MaxAry中最小的数(例如是MaxAry[100])比较。
如果这个数比MaxAry[100]小则读入下一个数继续比较。
如果比MaxAry[100]大的话,则将其排入MaxAry中适当位置,继续读入下个数……


算法解释:
10万个数中选出前100个大数,这意味着之后的数小于这100个数的概率是0.999,
也就是说1000个数中只有1个数需要插入MaxAry中。而随着读入数的个数增加,需
要插入MaxAry中的概率越小,效率也越来越高。相当于一个自学习的进化算法。

这个算法的理想前提是文件中的数据分布比较均匀,最差的情况是文件中的数据越往后越大。

 

(引用http://topic.csdn.net/u/20091013/10/d5d371dc-6dec-4034-bf31-432a47ffce96.html 254 楼geniuslinchao

 除了第一个回答无论是哪种方法,无疑,肯定是要将100g的文件读一遍的。而且是边写边处理

此外的回答还有多线程和分段排序再汇总比较。

关于多线程,我无法给出理由反驳。本身对多线程的知识就不牢靠所以不评论。

而分段排序再汇总我有疑问:如果分段后提取出来的最大的100个数字,比另一端里被舍弃的小数字还小呢?

基于上,我觉得还是要找好回答点。是100g?还是处理思路?

这个要看个人的思路。

以上回答,仅作提示。

原文地址:https://www.cnblogs.com/bukudekong/p/2029173.html