本文介绍了合并排序的数组的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
由于ķ排序阵列的每个长度为n,建立一个合并和分类array.focus上运行的时间和空间复杂度。
Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity.
来源:亚马逊面试问题
。有什么想法吗?谢谢
Source : Amazon interview question.
Any thoughts? thanks
推荐答案
从每个数组中的第一个元素做一个堆。从堆中弹出head元素,将其插入到结果数组,然后采取从堆的头来自数组的下一个元素,并插入到堆。重复,直到你消耗所有的阵列。
Make a heap from the first element in each array. Pop the head element from the heap, insert it into the result array, and then take the next element from the array the head of the heap came from, and insert that into the heap. Repeat until you consume all of the arrays.
这篇关于合并排序的数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!