Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Ссылка на сайт
трудность
Hard
описывать
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Учитывая K упорядоченных связанных списков, все его элементы должны быть объединены в связанный список и упорядочены.
Пример:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1- >1->2->3->4->4->5->6
отвечать
По соглашению, давайте сначала рассмотрим самое простое решение, которым является закон насилия.
Насилие
В этом вопросе метод насилия тоже очень простой, очень простой и грубый, то есть сначала вынуть все элементы, рассортировать их, а потом сложить в связанный список. Но, честно говоря, это немного пукает.Мы проанализируем сложность и обнаружим, что если количество всех элементов равно n, то итоговая сложность должна быть сложностью, потребляемой сортировкой, которая равна
, не имеет ничего общего с K, и мы не используем информацию о том, что все элементы в K связанных списках упорядочены, очевидно, это ненаучно.
Мы вносим некоторые оптимизации в приведенный выше метод чистого перебора и пытаемся использовать упорядоченную информацию об элементах в K связанных списках. Используемый метод также очень прост: раньше мы объединяли два массива, когда выполняли сортировку слиянием, мы использовали тот же метод, но на этот раз мы заменили его на K связанных списков. То есть каждый раз, когда мы проходим по головным элементам связанных списков K, мы вынимаем наименьший элемент и вставляем его в связанный список конечного результата.Когда все связанные списки пусты, это означает, что все элементы были объединены, а потом возвращаемся.
Давайте попробуем написать код:
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import sys
ret = ListNode(0)
pnt = ret
while True:
mini = sys.maxsize
node = None
# 遍历所有的链表
for i, l in enumerate(lists):
if l is None:
continue
if l.val < mini:
mini = l.val
node = i
# 如果node为None，说明所有的元素都已经归并结束了
if node is None:
break
pnt.next = ListNode(mini)
pnt = pnt.next
lists[node] = lists[node].next
return ret.next
Какова сложность этого алгоритма? После небольшого расчета мы знаем, что каждый раз, когда мы выбираем число, нам нужно пройти по головным указателям K связанных списков. Всего элементов n, поэтому общая сложность равна
. и предыдущие методы насилия
Как это сравнить? На самом деле это пол кэтти и восемь таэлей.Кто больше а кто меньше зависит всецело от К и
соотношение размеров. В общем случае n не будет превышать 10 миллионов, поэтому
Он будет не очень большим, по грубой оценке, не превысит 30, а K, скорее всего, превысит 30. То есть в большинстве случаев время вычисления этого метода больше, чем у грубой силы.
Кажется, что этот метод слияния, который использует отношение размеров элементов в связанном списке, не так эффективен, как простое и грубое насилие раньше. Это действительно прыщ.
сливаться
Давайте вспомним прошлое, в предыдущих задачах мы часто сталкивались со слиянием двух массивов, на этот раз это K связанный список, поэтому сложность сильно возросла. Так можем ли мы рассматривать эти K связанных списков как комбинацию двух связанных списков? Мы делим эти связанные списки каждый раз на две группы, а затем снова объединяем их в две группы, пока не останется только один связанный список.Будет ли эта схема лучше?
Давайте нарисуем картинку, чтобы увидеть процесс:
Глядя на него по горизонтали, на каждом этапе слияния мы прошли все элементы, поэтому общая сложность каждого слоя равна
. Итак, сколько всего слоев мы прошли? Это несложно, каждый раз при слиянии количество связанных списков будет уменьшаться вдвое. Всего имеется K связанных списков, поэтому, очевидно, их следует объединить.
раз, то есть есть
слияние этапов, поэтому общая сложность
. Поскольку K не будет слишком большим, этот метод, очевидно, лучше, чем
и
.
Давайте сначала напишем код для слияния двух связанных списков, а затем вызовем его рекурсивно:
class Solution:
def mergeTwoList(self, l1, l2):
ret = ListNode(0)
pnt = ret
while True:
"""
链表没办法像数组那样在末尾插入标兵了
所以只能人工判断是否为空的情况
"""
if l1 is None and l2 is None:
break
if l1 is None:
pnt.next = ListNode(l2.val)
pnt = pnt.next
l2 = l2.next
elif l2 is None:
pnt.next = ListNode(l1.val)
pnt = pnt.next
l1 = l1.next
else:
if l1.val < l2.val:
pnt.next = ListNode(l1.val)
l1 = l1.next
else:
pnt.next = ListNode(l2.val)
l2 = l2.next
pnt = pnt.next
return ret.next
def dfs(self, lists, l, r):
"""
递归合并K个链表
这里的l和r维护的是闭区间
"""
if l > r:
return None
if l == r:
return lists[l]
else:
mid = (l + r) // 2
return self.mergeTwoList(self.dfs(lists, l, mid), self.dfs(lists, mid+1, r))
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# 传入l=0， r=len(lists)-1，因为是闭区间
return self.dfs(lists, 0, len(lists)-1)
приоритетная очередь
Это еще не конец, я собираюсь представить лучшее решение этой проблемы, которое я лично считаю использованием приоритетной очереди, о которой мы упоминали ранее. Помните, что приоритетные очереди автоматически упорядочивают элементы в очереди. Просто используйте очередь с приоритетом, а затем используйте текущий первый элемент в качестве приоритета, и пусть очередь с приоритетом поможет нам поддерживать порядок в очереди. Благодаря использованию приоритетных очередей наш код значительно упрощается как с точки зрения удобочитаемости, так и сложности кодирования.
Если у вас есть новые проблемы или учащиеся, которые забыли об использовании приоритетной очереди, вы можете щелкнуть ссылку ниже, чтобы просмотреть использование приоритетной очереди:
Python использует библиотеку heapq для реализации приоритетной очереди
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
class Node:
"""
存储在优先队列当中的节点
"""
def __init__(self, val, arr):
self.val = val
self.arr = arr
# 重载判断大小的比较函数
def __lt__(self, other):
return self.val < other.val
import heapq
arr = []
# 将所有链表插入优先队列当中
for l in lists:
if l is not None:
heapq.heappush(arr, Node(l.val, l.next))
ret = ListNode(0)
pnt = ret
while len(arr) > 0:
# 从优先队列头部获取元素，需要注意，pop之后元素会从队列中删除
node = heapq.heappop(arr)
val, l = node.val, node.arr
pnt.next = ListNode(val)
pnt = pnt.next
# 获取完头部元素之后，将剩下的链表插入回队列当中
if l is not None:
heapq.heappush(arr, Node(l.val, l.next))
return ret.next
Этот способ намного меньше по сложности кода, чем предыдущий, но если мы его проанализируем, то обнаружим, что для приоритетной очереди сложность каждой вставки равна
, поскольку всего у нас есть K связанных списков, сложность вставки равна
, всего n элементов, поэтому окончательная сложность по-прежнему
Это так же, как слияние. Но использование структур данных упрощает процесс наших вычислений, поэтому и для чего мы изучаем различные структуры данных.
Хотя сложность этого вопроса на сегодняшний день Тяжелая, на самом деле он не сложный, даже если мы решим его насильно, мы сможем его пройти. Поэтому, надеюсь, вас не испугает написанная на ней сложность.Кроме того, эта задача тоже очень классическая для применения приоритетных очередей, и ее стоит изучить.
На сегодняшней статье все, если вы найдете что-то полезное, пожалуйстаОтсканируйте код и обратите вниманиеЧто ж, твое маленькое усилие много значит для меня.