Merge K Sorted Arrays

2016, Apr 25    

Merge K Sorted Arrays

@(算法)[算法, Heap, Priority Queue]

这一题怎样用一句话描述？

将K个有序数组合并成一个有序数组

用到什么算法？什么数据结构？

“排队出列法”，优先队列

通过这题学到了什么？

这一题我说它的算法是“排队出列法”，其实就是形容一下它的做法：将每个数组的首个元素按从小到大排成一列，让最小值出列，然后最小值所在数组的下一个元素入列，再重新排队，如此往复，直到队伍空了，我们的合并也就完成了。这是利用K个数组都已经排好序的特性。

当然，这个做法如果不用优先队列的话，时间复杂度是O(N * K)。用了优先队列后，由于每个元素只要入队一次，出队一次，入队的时间复杂度是O(log(K))，出队的时间复杂度是O(1)，所以总的时间复杂度是O(N * log(K))

可能(已经)遇到的BUG有？

由于我们不仅要记录一个元素的值，还要记录它的位置，所以必须自定义一个新的类型。但是java的priority queue的comparator是要自己实现的，千万别忘了实现，否则会默认按照int比较。