Merge k Sorted Arrays

Given k sorted integer arrays, merge them into one sorted array.

Given 3 sorted arrays:

[
  [1, 3, 5, 7],
  [2, 4, 6],
  [0, 8, 9, 10, 11]
]

return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

 这题和merge k sorted lists 一脉相承，但是处理起来要复杂些，即linked list可以非常容易的从当前结点通过.next找到它的下一个结点。但是arrays本身不可以，所以需要知道当前处理的是第几个数组，是这个数组中的什么位置。所以每次push进heap时同时要push进该元素来自第几个数组。但是这还不够，不知道具体在这个数组中是第几个位置。这里可以采取非常类似于Super Ugly Number的做法，维护一个times数组，表示当前处理到该数组的哪里了。代码如下：

class Solution:
    # @param {int[][]} arrays k sorted integer arrays
    # @return {int[]} a sorted array
    def mergekSortedArrays(self, arrays):
        import heapq
        if not arrays:
            return []
        heap = []
        indexs = [0] *len(arrays)
        for i in xrange(len(arrays)):
            if arrays[i]:
                heap.append((arrays[i][0],i))
        res = []
        heapq.heapify(heap)
        while heap:
            val, n = heapq.heappop(heap)
            res.append(val)
            indexs[n] += 1
            if indexs[n] < len(arrays[n]):
                heapq.heappush(heap,(arrays[n][indexs[n]],n))
        return res