Как объединить k отсортированных массивов, решение не работает, позволяя дубликаты.!

Question

Учитывая k отсортированных массивов размером n каждый, объедините их и напечатайте отсортированный вывод.

Алгоритм я следовал

• итерация по каждому массиву
  • выбрать i-й индекс в k массивах
  • 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]

Может ли кто-нибудь помочь мне узнать, чего не хватает в моем алгоритме, чтобы объединить дублирующиеся массивы во втором входе?

Answer 1

      from heapq import *

def mergeSort (arr):
    n = len(arr)
    minHeap = []
    
    for i in range(n):
        heappush(minHeap, (arr[i][0], i, arr[i]))
    
    print(minHeap)
    
    result = []
    while len(minHeap) > 0:
        num, ind, arr = heappop(minHeap)
        result.append(num)
        
        if len(arr) > ind + 1:
            heappush(minHeap, (arr[ind+1], ind+1, arr))
        
    
    return result
    
    

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

        ] 
        
print(mergeSort(input))

Answer 2

Чтобы исправить свой код, переместите 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 элементов, по одному элементу из каждого списка, а новый элемент, добавляемый вами на каждом шаге, должен исходить из исходного списка только что извлеченного элемента.,