0

给定 k 个大小为 n 的排序数组，合并它们并打印排序后的输出。

我遵循的算法是

  • 遍历每个数组
    • 选择 k 个数组中的第 i 个索引
    • insert()在最小堆中
    • delMin()并附加结果数组。

from heapq import heappop, heappush

def merge_k_arrays(list_of_lists):
    result = [] #len(list_of_lists[0])*len(list_of_lists)
    minHeap= []
    n, k=0,0

    print(list_of_lists)
    while n < len(list_of_lists[0]):
        if n ==0:# initial k size heap ready
            while k < len(list_of_lists):
                element= list_of_lists[k][n]
                heappush(minHeap ,element )
                k+=1
            result.append(heappop(minHeap))
        else: # one at a time.
            k =0
            while k < len(list_of_lists):
                element = list_of_lists[k][n]
                heappush(minHeap , element)
                result.append(heappop(minHeap))
                k+=1
        n += 1

    # add the left overs in the heap
    while minHeap:
        result.append(heappop(minHeap))

    return result

输入：

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

        ]

输出：

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

输入：

input = [   [1, 3, 5, 7],
            [2, 4, 6, 8],
            [3, 3, 3, 3],
            [7, 7, 7,7]
        ]

输出：

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

任何人都可以帮我知道我的算法中缺少什么，以便合并第二个输入中的重复数组吗？

4

1 回答 1

-1

要修复代码，请将result.append(heappop(minHeap))第二个嵌套 while 循环中的 移到嵌套 while 循环的外部，就像在第一个嵌套 while 循环中一样。这将使您的代码工作。

        else: # one at a time.
        k =0
        while k < len(list_of_lists):
            element = list_of_lists[k][n]
            heappush(minHeap , element)

            k+=1
        result.append(heappop(minHeap))
    n += 1

如果您有任何空间限制，这仍然是个问题，因为您几乎将整个输入添加到堆中。如果空间不是问题，那么有一种更简洁的方法来编写您的解决方案：

def merge(A):
    result = []
    heap = [e for row in A for e in row]
    heapify(heap)
    for i in range(len(heap)):
        result.append(heappop(heap))
    return result

否则，您将需要使用更智能的解决方案，只允许堆总共有 k 个元素，每个列表中包含一个元素，并且您在每一步添加的新元素应该来自刚刚弹出的元素的原始列表.

于 2018-11-23T02:41:31.850 回答