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

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

0 голосов
/ 23 ноября 2018

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

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

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

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

1 Ответ

0 голосов
/ 23 ноября 2018

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

...