作为Mergesort算法的一部分,广泛研究了双向合并.但我有兴趣找出一个可以执行N路合并的最佳方式吗？
可以说,我有一些N文件,每个文件已经排序了100万个整数.我必须将它们合并为1个单独的文件,这将有1亿个排序整数.
请记住,此问题的用例实际上是基于磁盘的外部排序.因此,在实际场景中也会存在内存限制.因此,一次合并2个文件(99次)的天真方法将无效.假设我们每个阵列只有一个小的可用内存滑动窗口.
我不确定是否已经存在这种N路合并的标准化解决方案.(谷歌搜索并没有告诉我太多).
但是如果你知道一个好的n路合并算法,请发布algo/link.
时间复杂度:如果我们大大增加N要合并的文件()的数量,那将如何影响算法的时间复杂度？
谢谢你的回答.
我没有被问过这个问题,但我觉得这可能是一个有趣的面试问题.因此标记.
这是一个谷歌面试问题:
给定N*N矩阵.对所有行进行排序,并对所有列进行排序.找到矩阵的第K个最大元素.
在n ^ 2中执行它很简单,我们可以使用堆或合并排序(n lg n)对其进行排序然后得到它,但是有更好的方法,比(n lg n)更好吗？
数组示例::
1 5 7 12
3 6 8 14
4 9 10 15
11 17 19 20
与其他行和列类似,1 <5 <7 <12和1 <3 <4 <11.现在说我们需要找到第10个最小的元素,在这里它是11..hope这增加了一些细节问题......
如何在Ruby中懒洋洋地合并N个排序数组(或其他类似列表的数据结构)？例如,在Python中,您将使用heapq.merge.Ruby中必须有这样的内容,对吧？