Merge k Sorted Lists

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

С минимальной кучей это O(N log k) , где N — общее количество значений, а k — количество списков. Каждое значение добавляется и извлекается один раз, а куча содержит не более k элементов, поэтому каждая операция стоит O(log 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]
Пояснение: Наименьшее значение в целом — 1, первое значение во второй строке. После него строки начинаются с 2, 4 и 3, поэтому следующим идет 2, и так далее. В третьей строке значения заканчиваются на 5, после чего в конце остаются 6, 9 и 10.

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

+14 скрытых тестов при отправке

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

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

Решение

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

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

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

Идея

Храни по одному индексу для каждой строки — pos[r], указывающему на первое ещё не использованное значение строки r: её начало. Наименьшее из всех неиспользованных значений обязательно будет одним из этих первых значений. В строке r каждое неиспользованное значение находится на позиции pos[r] или дальше, а строка отсортирована, поэтому ни одно из них не меньше первого.

Найди наименьшее первое значение среди всех строк, в которых ещё есть значения, добавь его в результат и передвинь индекс этой строки на одну позицию вперёд. Повторяй, пока не будут извлечены все N значений. Это этап слияния сортировки слиянием, расширенный с двух списков до k.

В первом примере первые значения сначала равны 2, 1 и 3, поэтому первым извлекается 1, а первым значением второй строки становится 4. Затем извлекается 2 (первые значения: 2, 4, 3), потом 3 (первые значения: 6, 4, 3), затем 4, а потом 5, после чего третья строка опустеет. В последних трёх раундах сравниваются только 6 и 10, затем 9 и 10, а затем только 10.

Для каждого из N значений требуется k сравнений. При 10^4 строках, содержащих по одному значению, это 10^8 сравнений. C, Java или JavaScript справятся с ними менее чем за секунду, но Python потребуется больше десяти секунд, а удвоение и N, и k замедляет работу любого языка в четыре раза. Это видно по трассировке: после каждого выбора изменяется только одно первое значение, но в следующем раунде снова считываются все k значений.

Алгоритм

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

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

Проследи за первым примером, нумеруя строки с 0. Вначале в куче находятся 2 (строка 0), 1 (строка 1) и 3 (строка 2). Извлекаем 1 и добавляем следующее значение строки 1 — 4. Извлекаем 2 и добавляем 6 из строки 0. Извлекаем 3 и добавляем 5 из строки 2. Извлекаем 4 и добавляем 10. Извлекаем 5: значения в строке 2 закончились, поэтому ничего не добавляем, и в куче остаются 6 и 10. Извлекаем 6 и добавляем 9. Извлекаем 9, затем 10. Результат: [1, 2, 3, 4, 5, 6, 9, 10].

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

В нескольких версиях кучу строят вручную — в массиве номеров строк, упорядоченных по головному элементу каждой строки. Дочерние элементы ячейки i находятся в ячейках 2i+1 и 2i+2 (в 2i и 2i+1 в Lua и R, где нумерация начинается с 1). Это также позволяет сократить количество операций: после извлечения головного элемента строки, стоящей на вершине, следующее значение этой строки не меньше, поэтому строка остаётся на вершине и просеивается вниз один раз — вместо извлечения с последующим добавлением.

Алгоритм

Помести (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. В Java PriorityQueue и в Python heapq уже возвращают наименьшее значение.
Равные значения в Python heapq. Когда два значения равны, сравнение кортежей переходит ко второму элементу. Номера строк сравниваются без проблем, а узлы связанного списка — нет, и классическая версия аварийно завершается при равных значениях. Поместите номер строки или счётчик на второе место.
Помещать все значения в кучу в самом начале. Сортировка всё равно будет правильной, но куча вырастет до N элементов, а сложность работы станет O(N log N). Храните по одному первому элементу для каждой строки.
Читать за концом короткой строки. Длина строк различается, поэтому перед добавлением следующего значения проверьте, есть ли оно в строке.
Отбрасывать дубликаты. Равные значения из разных строк являются отдельными значениями, и все они должны попасть в результат.

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

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

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

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

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

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

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

Почему куче нужна только голова каждого списка?

Каждый список отсортирован, поэтому его первое неиспользованное значение — наименьшее из оставшихся в нём. Следовательно, наименьшее значение среди всех списков — это наименьшее из их первых элементов, и ни одно значение, расположенное глубже в списке, не может быть меньше. Когда первый элемент извлекается, следующее значение из того же списка становится его первым элементом и занимает его место в куче.

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

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