Как обычно, в этой записи блога мы попрактикуемся в решении задач алгоритмов. И сегодня наша проблема с leetcode: Объединить k отсортированных списков.

Определение проблемы:

Объединить k отсортированных связанных списков и вернуть его как один отсортированный список.

Пример:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

Два отсортированных списка

В случае только двух отсортированных списков мы можем использовать простой двоичный поиск с двумя указателями. Аналогично тому, как мы поступили с проблемой медианы двух отсортированных списков. Но когда у нас есть 3 или более списков для перебора, это становится немного сложнее.

K отсортированных списков

Сначала давайте проверим, сколько списков у нас во входных данных. Это поможет нам определить, сколько указателей нам нужно. В случае двух списков мы можем просто жестко закодировать два указателя, и это будет работать. Но для неизвестного количества списков нам понадобится другой способ отслеживания указателей и их позиций.

Также у нас будет проблема возрастающей сложности сравнения. В случае двух списков нам нужно будет провести только одну операцию сравнения, в случае 4-х списков, 4-х операций и так далее. Если у нас есть 100 списков, это становится немного менее элегантным для условий жесткого кода. Нам нужно будет придумать умный способ одновременного сравнения всех чисел.

Временная сложность выполнения K сравнений на каждой итерации:

O(N * K * K)

Временная сложность алгоритма сортировки:

O(N * K * log(N * K))

Становится более эффективным объединение всех списков в один длинный список с последующим написанием алгоритма сортировки этого списка.

Встаньте в очередь по двое

Сначала давайте напишем цикл while, который объединит все списки, независимо от того, сколько списков у нас на входе. Мы собираемся работать с двумя списками одновременно и будем продолжать до тех пор, пока длина входных списков не станет больше 1.

Функция слияния

Как видно на картинке выше, мы рекурсивно используем mergeLists. Эта функция отвечает за сортировку и объединение двух списков одновременно. Помните, что эти списки уже отсортированы по отдельности, что означает, что мы можем выполнять простой двоичный поиск по ним. Мы собираемся использовать другой цикл while, который будет работать до тех пор, пока списки a или b не станут нулевыми. Внутри цикла у нас есть условие, и если a меньше, чем b, мы обновляем указатель и переходим к следующему значению списка, и оно больше, затем мы обновляем указатель и переходим к следующему значению списка b. Вот как выглядит функция margeLists:

Решение

После того, как все списки объединены и отсортированы, в переменной списков остается только один список. И мы возвращаем индекс 0 в этой переменной.

Заключение

Для инженеров-программистов важна работа с различными структурами данных. Вот что leetcode думает об эффективности нашего решения:

Похоже, эффективность нашего решения могла бы быть лучше. Я продолжу работать над оптимизацией и попробую разные подходы к решению этой проблемы. Будьте на связи!

Продолжайте учиться, продолжайте расти!

Присоединяйтесь к LinkedIn!