Merge k Sorted Lists

Q: Какова временная сложность объединения k отсортированных списков?

При использовании минимальной кучи сложность составляет O(N log k) , где N — общее количество значений, а k — количество списков. Каждое значение добавляется в кучу и извлекается из неё один раз, а куча содержит не более k элементов. Дополнительная память, помимо памяти для результата, составляет O(k) .

Q: Почему бы не объединить все значения и отсортировать их?

Это верно и занимает время O(N log N) . При этом не учитывается, что списки уже отсортированы, поэтому для каждого значения затрачивается log N , тогда как куча затрачивает log k , и все значения должны одновременно находиться в памяти. Куча также может объединять списки, поступающие в виде потоков.

СложноКуча Связный список

+10

Даны k списков целых чисел в качестве строк lists. Каждая строка отсортирована в неубывающем порядке, строки могут иметь разную длину, и ни одна строка не пуста.

Объедините их в один список, содержащий все значения из каждой строки, отсортированный в неубывающем порядке, и верните его. Значение, которое встречается несколько раз — в одной или нескольких строках, — должно встречаться в результате столько же раз.

Функция

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: отсортированные списки, по одному в каждой строке, возможно, разной длины
Возвращаетinteger-array: все значения из каждой строки в одном отсортированном списке

Ограничения

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, и все строки вместе содержат не более 10⁴ значений
-10⁴ ≤ lists[i][j] ≤ 10⁴
Каждая строка отсортирована в порядке неубывания.

Примеры

Ввод: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Вывод: [1, 2, 3, 4, 5, 6, 9, 10]
Пояснение: Строки начинаются с 2, 1 и 3, поэтому сначала идёт 1. Затем в начале стоят 2, 4 и 3, поэтому следующим идёт 2 и так далее. В третьей строке числа заканчиваются после 5, остаются 6, 9 и 10.

Ввод: lists = [[5], [-2, 5, 7], [0, 5]]
Вывод: [-2, 0, 5, 5, 5, 7]
Пояснение: Три числа 5 взяты из трёх разных строк, и все три остаются. Отрицательное число -2 сортируется перед 0.

Дополнительный вопрос

Найдите наименьший диапазон [a, b], содержащий значение из каждой строки. Можно ли решить эту задачу с помощью кучи первых элементов строк и наибольшего первого элемента за O(N log k)?

Решение

Каждая строка отсортирована, поэтому наименьшее неиспользованное значение всегда является первым неиспользованным значением в какой-либо строке — её головным элементом. Просмотр всех k головных элементов требует k шагов для каждого из N значений. Мин-куча из головных элементов выдаёт наименьший за O(log k), что сокращает общую сложность с O(N·k) до O(N log k).

Сравните все k голов для каждого значения

Верно, но не успевает на самых больших тестах

Идея

Храните индекс pos[r] в начале каждой строки. На каждом шаге считывайте все первые элементы, добавляйте наименьший и продвигайте индекс этой строки: это шаг слияния сортировки слиянием, расширенный с двух списков до k. В первом примере первые элементы — 2, 1 и 3, поэтому первым выходит 1, а первым элементом второй строки становится 4.

Для каждого из N значений требуется проход по всем k строкам. Если в 10^4 строках по одному значению, это 10^8 проверок строк.

Алгоритм

Установите pos[r] = 0 для каждой строки и подсчитайте количество значений, N.
Повторите N раз: просмотрите все строки, в которых pos[r] всё ещё указывает на элемент, и запомните строку с наименьшим первым элементом.
Добавьте этот первый элемент в результат и увеличьте pos этой строки на 1.
Верните результат.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

Мин-куча из k голов

Идея

После каждого извлечения изменяется только один первый элемент, но при сканировании заново считываются все k элементов. Мин-куча хранит первые элементы так, что на вершине находится наименьший. Пометьте каждый первый элемент номером его строки, чтобы после извлечения (value, row) вы знали, какое следующее значение из этой строки нужно добавить. В куче всегда хранится по одной записи на каждую строку, в которой ещё остались значения, поэтому на вершине находится наименьшее неиспользованное значение.

В первом примере в куче изначально находятся 2, 1 и 3. Извлекаем 1, добавляем 4. Извлекаем 2, добавляем 6. Извлекаем 3, добавляем 5. Извлекаем 4, добавляем 10. Извлекаем 5: третья строка исчерпана, поэтому ничего не добавляем. Извлекаем 6, добавляем 9, затем извлекаем 9 и 10.

Каждое значение добавляется и извлекается один раз, а в куче никогда не бывает больше k элементов: 2N операций сложности O(log k). При N = k = 10^4 это меньше 3 × 10^5 шагов. Куча занимает O(k) памяти.

Алгоритм

Добавьте (lists[r][0], r) в минимальную кучу, упорядоченную по значению, для каждой строки r.
Пока куча не пуста, извлекайте наименьшую пару (value, r) и добавляйте value в результат.
Если в строке r есть следующее значение, добавьте его вместе с r.
Верните результат, когда куча опустеет.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

Ловушки и крайние случаи

Добавление только значений. После извлечения элемента нельзя определить, какую строку продвинуть. Храните строку вместе со значением.
Случайное использование max-кучи. C++ priority_queue и Rust BinaryHeap помещают на вершину наибольший элемент; используйте greater<> или Reverse.
Добавление всех значений в начале. Результат всё равно будет отсортирован, но куча вырастет до N элементов, а трудоёмкость составит O(N log N).
Чтение за пределами короткой строки. В первом примере в третьей строке два значения, поэтому перед добавлением проверьте, есть ли следующее значение.
Удаление дубликатов. Три значения 5 во втором примере — это отдельные значения, и все они должны попасть в результат.

Частые вопросы3

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

При использовании минимальной кучи сложность составляет O(N log k), где N — общее количество значений, а k — количество списков. Каждое значение добавляется в кучу и извлекается из неё один раз, а куча содержит не более k элементов. Дополнительная память, помимо памяти для результата, составляет O(k).

Почему бы не объединить все значения и отсортировать их?

Это верно и занимает время O(N log N). При этом не учитывается, что списки уже отсортированы, поэтому для каждого значения затрачивается log N, тогда как куча затрачивает log k, и все значения должны одновременно находиться в памяти. Куча также может объединять списки, поступающие в виде потоков.

Можешь ли ты объединить k отсортированных списков без кучи?

Да, методом «разделяй и властвуй». Объединяй списки попарно, используя слияние двух списков, затем попарно объединяй результаты и так далее: log k раундов, в каждом из которых каждое значение затрагивается один раз, то есть O(N log k). Объединять списки по одному в растущий результат медленнее: O(N·k), потому что ранние значения копируются заново при каждом слиянии.

def mergeKLists(lists):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

Ожидаемый вывод

[1, 2, 3, 4, 5, 6, 9, 10]