经典指数          
原因
2249
浏览数
0
收藏数
 

linux32位系统下有10个无序文件,各文件大小不一(均小于1G)现在需要将此10个文件归并为一组,不超过10个有序文件(第一个文件最大数小于或等于第二个文件最小数,依次类推)请选择你擅长的语言实现说明。 文件的每一行最大不超过128位的阿拉伯数字组合,每一行只有一个数字,头一位不是零要求写出思路和程序,计算时间复杂度和空间复杂度。

     举报   纠错  
 
切换
1 个答案

顺序读文件中,对于每个词x,取

,然后按照该值存到5000个小文件(记为

)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了

 
切换
撰写答案