Постановка задачи
Вам дан массив из k связанных списков lists, каждый связанный список отсортирован в порядке возрастания.
Объединить все связанные списки в один отсортированный связанный список и вернуть его.
Постановка задачи взята с: https://leetcode.com/problems/merge-k-sorted-lists
Пример 1:
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6Пример 2:
Input: lists = []
Output: []Пример 3:
Input: lists = [[]]
Output: []Ограничения:
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10^4.Решения для проблемы слияния отсортированных списков
Подход 1: грубая сила
В одном из предыдущих постов мы обсуждали, как Сортировать один связанный список. В этой задаче нам нужно объединить K отсортированный связанный список.
Простым решением было бы соединить все k связанных списков в один список (в любом порядке). Затем используйте алгоритм сортировки слиянием, описанный в статье Список сортировки. Временная сложность этого подхода в наихудшем случае составляет O(n * log(n)), где n — общее количество узлов, присутствующих во всех k списках. Этот подход неэффективен, поскольку мы не используем преимущества уже отсортированных списков.
Давайте проверим фрагмент C++ этого подхода ниже:
ListNode* getLastNode(ListNode* head) {
ListNode* current = head;
ListNode* next = current->next;
while(next != NULL) {
current = next;
next = current->next;
}
return current;
}
// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return NULL;
}
// connect all k sorted linked lists into one list
for(int i = 0; i < lists.size() - 1; i++) {
// fetch the last node
ListNode* last = getLastNode(lists[i]);
last->next = lists[i + 1];
}
// perform merge sort on list[0]
return sortList(lists[0]);
}
// merge sort the two list
ListNode* mergelist(ListNode *l1, ListNode *l2) {
ListNode *ptr = new ListNode(0);
ListNode *current = ptr;
while(l1 != NULL && l2 != NULL) {
if(l1->val <= l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
if(l1 != NULL) {
current->next = l1;
l1 = l1->next;
}
if(l2 != NULL) {
current->next = l2;
l2 = l2->next;
}
return ptr->next;
}
ListNode* sortList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode *temp = NULL;
ListNode *slow = head;
ListNode *fast = head;
// split the list into two halves
while(fast != NULL && fast->next != NULL) {
temp = slow;
slow = slow->next;
fast = fast->next->next;
}
temp->next = NULL;
// recursively call the sortList function for the two lists
ListNode* l1 = sortList(head);
ListNode* l2 = sortList(slow);
// merge list l1 and l2
return mergelist(l1, l2);
}
Второй метод грубой силы для решения проблемы заключается в объединении двух отсортированных списков одновременно. Мы объединяем первые два списка lists[0] с lists[1] и сохраняем результат. Мы объединяем результат с третьим списком lists[2] и повторяем процесс k — 1 раз.
Этот метод относительно прост. Но временная сложность этого подхода составляет O(n * k), где n — количество объединяемых элементов.
Фрагмент C++ этого подхода выглядит следующим образом:
// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return NULL;
}
return mergeKSortedListsHelper(lists);
}
// Helper function to merge k sorted lists
ListNode* mergeKSortedListsHelper(vector<ListNode*>& lists) {
int size = lists.size();
// Traverse from the second list to last
for (int i = 1; i <= size; i++) {
while(true) {
ListNode head1 = lists[0], head2 = lists[i];
// if the list has ended
if(head1 == NULL) {
break;
}
if(head1->val >= head2->val) {
lists[i] = head2->next;
head2->next = head1;
lists[0] = head2;
} else {
// Traverse the first list
while (head1->next != NULL) {
// find the node in the first list which is just
// greater than second list current node
if (head1->next->val >= head2->val) {
lists[i] = head2->next;
head2->next = head1->next;
head1->next = head2;
break;
}
head1 = head1->next;
}
if(head1->next == NULL) {
lists[i] = head2->next;
head2->next = NULL;
head1->next = head2;
head1->next->next = NULL;
break;
}
}
}
}
return lists[0];
}
Временная сложность двух вышеупомянутых подходов очень высока, поскольку мы не используем преимущества отсортированных списков. Мы можем оптимизировать подход, используя дополнительную структуру данных: Min Heap.
Подход 2: использование минимальной кучи
Мы можем оптимизировать описанный выше подход, используя Min Heap. Корень Min Heap всегда является наименьшим элементом.
Согласно постановке задачи, все связанные списки отсортированы. Следовательно, первый элемент списка будет наименьшим. Мы добавляем первые элементы всех связанных списков в Min Heap. Мы извлекаем наименьший элемент, корень Min Heap. После удаления корня мы увеличиваем указатель списка, которому принадлежал корневой элемент. Следующий узел этого списка добавляется в Min Heap. Мы продолжаем удалять корень и продолжаем добавлять следующий узел из списков в кучу, пока не будут пройдены все списки и куча не станет пустой.
Этот алгоритм также можно использовать для объединения K отсортированных массивов. Временная сложность алгоритма составляет O(n * log(k)). Где n — количество элементов во всех списках, а k — количество связанных списков. Сложность пространства составляет O(k), где k — размер минимальной кучи.
Давайте проверим алгоритм этого подхода.
- priority_queue<ListNode*, vector<ListNode*>, compare> pq
- for int i = 0; i < k; i++
- if lists[i] != NULL
- pq.push(arr[i])
- if end
- for end
- if pq.empty()
- return NULL
- if end
- ListNode* result = new ListNode(0)
ListNode* last = dummp
- loop while !pq.empty()
- ListNode* current = pq.top()
pq.pop()
- last->next = current
last = last->next
- if current->next != NULL
pq.push(curr->next)
- if end
- while end
- return result->nextДавайте проверим алгоритм в коде C++.
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
int k = lists.size();
// Push the first nodes of all the k lists in priority_queue 'pq'
for (int i = 0; i < k; i++)
if (lists[i] != NULL)
pq.push(lists[i]);
if (pq.empty())
return NULL;
ListNode *result = new ListNode(0);
ListNode *last = result;
// Loop till 'pq' is not empty
while (!pq.empty()) {
// Get the top element of 'pq'
ListNode* current = pq.top();
pq.pop();
// Add the top element of 'pq' to the result list
last->next = current;
last = last->next;
// If the current next node is not NULL, add it to the priority queue
if (current->next != NULL) {
pq.push(curr->next);
}
}
// return the result
return result->next;
}
Подход 3: использование принципа «разделяй и властвуй»
Используя Min Heap, мы сократили временную сложность до O(n * log(k)), но для кучи требуется O(k) дополнительного места. Мы можем решить эту проблему в постоянном пространстве, используя метод «разделяй и властвуй».
Как упоминалось в нашем методе Brute force, мы знаем, как объединить два отсортированных списка. Идея состоит в том, чтобы объединить k списков и объединить каждую пару за линейное время, используя пространство O(1). После первой итерации осталось k/2 списков размера 2 * n. После второго цикла остается k/4 списков. Повторяем процедуру, пока у нас не останется один список.
Сначала проверим алгоритм.
// function mergeKLists(vector<ListNode*>& lists)
- if lists.size() == 0
- return NULL
- if end
- return mergeKListsHelper(lists, lists.size() - 1)
// function mergeKListsHelper(vector<ListNode*>& lists, int last)
// Merge lists until one list is left
- loop while last != 0
- initilaize i = 0, j = last
- loop while i < j
// merge list i with list j
// store the merged result in list i
- lists[i] = mergeLists(lists[i], lists[j])
- increment i = i++
- decrement j = j--
- if i >= j
- last = j
- if end
- while end
- while end
- return lists[0]
// function mergeLists(ListNode* l1, ListNode* l2)
- set ListNode* head = NULL
- if l1 == NULL
- return l2
- else if l2 == NULL
- return l1
- if end
- if l1->val < l2->val
- set head = l1
- set l1 = l1->next
- else
- set head = l2
- set l2 = l2->next
- if end
- set ListNode* p = head
- loop while l1 && l2
- if l1->val < l2->val
- set p->next = l1
- set l1 = l1->next
- else
- set p->next = l2
- set l2 = l2->next
- if end
- set p = p->next
- while end
- if l1 != NULL
- p->next = l1
- else
- p->next = l2
- if end
- return headВременная сложность описанного выше подхода составляет O(n * log(k)), а пространственная сложность — O(1).
Давайте проверим наши решения на C++, Golang и Javascript.
С++ решение
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return NULL;
}
return mergeKListsHelper(lists, lists.size() - 1);
}
ListNode* mergeKListsHelper(vector<ListNode*>& lists, int last) {
// Merge lists until one list is left
while(last != 0) {
int i = 0, j = last;
while(i < j) {
// merge list i with list j
// store the merged result in list i
lists[i] = mergeLists(lists[i], lists[j]);
i++;
j--;
// update last when all pairs are merged
if(i >= j) {
last = j;
}
}
}
return lists[0];
}
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
ListNode* head = NULL;
// if any one of the two lists is empty
// return the other list.
if(l1 == NULL) {
return l2;
} else if(l2 == NULL) {
return l1;
}
// choose the head based on the smallest value of two lists.
if(l1->val < l2->val){
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
ListNode *p;
p = head;
while(l1 && l2){
if(l1->val < l2->val){
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if(l1 != NULL){
p->next = l1;
} else {
p->next = l2;
}
return head;
}
};
Голанг решение
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil;
}
return mergeKListsHelper(lists, len(lists) - 1)
}
func mergeKListsHelper(lists []*ListNode, last int) *ListNode {
// Merge lists until one list is left
for last != 0 {
i, j := 0, last
for(i < j) {
// merge list i with list j
// store the merged result in list i
lists[i] = mergeLists(lists[i], lists[j])
i++;
j--;
// update last when all pairs are merged
if i >= j {
last = j
}
}
}
return lists[0]
}
func mergeLists(l1, l2 *ListNode) *ListNode {
var head *ListNode
head = nil
// if any one of the two lists is empty
// return the other list.
if l1 == nil {
return l2
} else if l2 == nil {
return l1
}
// choose the head based on the smallest value of the two lists.
if(l1.Val < l2.Val){
head = l1;
l1 = l1.Next;
} else {
head = l2;
l2 = l2.Next;
}
p := head
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
p.Next = l1
l1 = l1.Next
} else {
p.Next = l2
l2 = l2.Next
}
p = p.Next
}
if l1 != nil {
p.Next = l1
} else {
p.Next = l2
}
return head
}
JavaScript-решение
var mergeKLists = function(lists) {
if(lists.length === 0) {
return null;
}
return mergeKListsHelper(lists, lists.length - 1);
};
var mergeKListsHelper = function(lists, last) {
// Merge lists until one list is left
while(last != 0) {
let i = 0, j = last;
while(i < j) {
// merge list i with list j
// store the merged result in list i
lists[i] = mergeLists(lists[i], lists[j]);
i++;
j--;
// update last when all pairs are merged
if(i >= j) {
last = j;
}
}
}
return lists[0];
};
var mergeLists = function(l1, l2) {
let head = null;
// if any one of the two lists is empty
// return the other list.
if(l1 == null) {
return l2;
} else if(l2 == null) {
return l1;
}
// choose the head based on the smallest value of the two lists.
if(l1.val < l2.val){
head = l1;
l1 = l1.next;
} else {
head = l2;
l2 = l2.next;
}
let p = head;
while(l1 && l2){
if(l1.val < l2.val){
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if(l1 != null){
p.next = l1;
} else {
p.next = l2;
}
return head;
};
Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
// mergeKLists function
Step 1: if lists.size() == 0
3 == 0
false
Step 2: return mergeKListsHelper(lists, lists.size() - 1)
mergeKListsHelper(lists, 2)
// mergeKListsHelper
Step 3: loop while last != 0
2 != 0
true
i = 0
j = last
= 2
loop while i < j
0 < 2
true
lists[i] = mergeLists(lists[i], lists[j])
lists[0] = mergeLists(lists[0], lists[2])
= mergeLists([1, 4, 5], [2, 6])
// mergeLists([1, 4, 5], [2, 6])
Step 4: This function will merge the list and return
[1, 2, 4, 5, 6]
// mergeKListsHelper
Step 5: i++
i = 1
j--
j = 1
if i >= j
1 >= 1
true
last = j
last = 1
loop while i < j
1 < 1
false
// mergeKListsHelper
Step 6: loop while last != 0
1 != 0
true
i = 0
j = last
= 1
loop while i < j
0 < 1
true
lists[i] = mergeLists(lists[i], lists[j])
lists[0] = mergeLists(lists[0], lists[1])
= mergeLists([1, 2, 4, 5, 6], [1, 3, 4])
// mergeLists([1, 2, 4, 5, 6], [1, 3, 4])
Step 7: This function will merge the list and return
[1, 1, 2, 3, 4, 4, 5, 6]
// mergeKListsHelper
Step 8: i++
i = 1
j--
j = 0
if i >= j
1 >= 0
true
last = j
last = 0
loop while i < j
1 < 0
false
Step 9: loop while last != 0
0 != 0
false
Step 10: return lists[0]
[1, 1, 2, 3, 4, 4, 5, 6]Первоначально опубликовано на https://alkeshghorpade.me.
