合并排序的数组 [英] merging sorted arrays

问题描述

可能显示的文件：
  合并两个排序列表
  算法N路合并

Possible Duplicates:
Merging two sorted lists
Algorithm for N-way merge

由于ķ排序阵列的每个长度为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.

这篇关于合并排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！