Как объединить количество отсортированных списков?

Question

def merge(list1, list2):
    results = []
    while list1 and list2:
        if list1[0] < list2[0]:
            results.append(list1.pop(0))
        else:
            results.append(list2.pop(0))
    results.extend(list1)
    results.extend(list2)
    return results

Вот стандартный алгоритм объединения 2 отсортированных списков в 1. Однако, как мы можем объединить несколько отсортированных списков в 1?

l = [[8, 10, 12], [4, 5, 9], [2, 11]]  
merge(l)  
>>> [2, 4, 5, 8, 9, 10, 11, 12]

Answer 1

from Queue import PriorityQueue

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        head = point = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put((l.val, l))
        while not q.empty():
            val, node = q.get()
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                q.put((node.val, node))
        return head.next

Использование очереди приоритетов оптимизирует процесс сравнения

1. Сложность времени: O (n log (k)), где k - количество связанных списков:

   • Стоимость сравнения будет уменьшена до O (log k) для каждого всплывающего окна и вставки в приоритетную очередь.Но поиск узла с наименьшим значением просто стоит O (1) времени.

2. Пространство сложности:

   • O (n) Создание новогосвязанный список стоит O (n) места
   • O (k) Приведенный выше код применяет метод на месте, который стоит O (1) места.
   • И очередь приоритетов (часто реализуемая с кучами)) стоит O (k) места (в большинстве случаев это намного меньше, чем N)

Answer 2

Свести со списком, а затем отсортировать

print(sorted([j for i in l for j in i]))
# [2, 4, 5, 8, 9, 10, 11, 12]

Answer 3

Вы можете использовать свои собственные merge с reduce:

from functools import reduce

l = [[8, 10, 12], [4, 5, 9], [2, 11]]

merged = reduce(merge, l)
print(merged)
# [2, 4, 5, 8, 9, 10, 11, 12]

Это время работы O (kn) .Вы можете объединять (уникальные) пары, пока у вас не останется 1 последний список, что улучшит его до O (n log k) (так как количество списков, которые нужно объединить, уменьшается наполовину каждый раз).

Answer 4

Вы можете реализовать прямое k-way merge , используя heap и очереди :

import heapq
from collections import deque


def k_merge(*lists):
    queues = [queue for queue in map(deque, lists)]

    heap = []
    for i, lst in enumerate(queues):
        heap.append((lst.popleft(), i))

    heapq.heapify(heap)

    result = []
    while heap:
        value, index = heapq.heappop(heap)
        result.append(value)

        if queues[index]:
            heapq.heappush(heap, (queues[index].popleft(), index))

    return result


print(k_merge(*[[8, 10, 12], [4, 5, 9], [2, 11]]))

Выход

[2, 4, 5, 8, 9, 10, 11, 12]

Если у вас есть k списки и n элементов, этот подход будет O(nlogk)

Answer 5

Вы можете просто отсортировать его, используя sorted():

from itertools import chain

l = [[8, 10, 12], [4, 5, 9], [2, 11]]

sorted(chain(*l))

Дает результат:

[2, 4, 5, 8, 9, 10, 11, 12]