力扣题解:23.合并K个升序链表(困难)
前言
这道题是合并两个有序链表的升级版,理论层面的难度并不算大,在编码过程中可能涉及到一些深一些的知识点,本题采用了优先队列,并自定义了比较器实现小顶堆。
该题涉及:
- 优先队列
题目
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
提示:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i]
按升序排列lists[i].length
的总和不超过10^4
思路:我们思考对两个链表进行合并,有以下过程,我们总是采取两个链表中值较小的一个进行合并操作。
1->3->4 3->4 3->4 3->4 3->4 null
-> -> -> -> ->
1->1->2 1->1->2 1->2 2 null null
null -> 1 -> 1->1 -> 1->1->1 -> 1->1->1->2
-> 1->1->1->2->3->4
对于k个链表,我们当然可以两两合并,但是这样会重复遍历很多元素。能不能一次合并k个链表呢?
我们考虑对于两个链表的合并,我们总是拿值较小的一个进行合并,拓展至k个链表,那就是我们拿值最小的一个进行合并操作。
例如有3个链表的合并,我们总是拿三个链表头节点中值最小的一个进行合并操作。
1->3 3 3 3 null
-> -> -> -> -> ...
2->3 2->3 2->3 3 3
-> -> -> -> -> ...
1->4 1->4 4 4 4
null -> 1 -> 1->1 -> 1->1->2 -> 1->1->2->3 -> ...
原理到这部分就结束了,到了编码问题,我们采用优先队列来实现。
priority_queue
是优先队列,其队首元素总是最大或最小的,维护其有序性的时间复杂度为O(logn)
,采用堆的方式进行排序,这样我们每次都能很快的拿到最小的那个元素。
题解:
- 时间复杂度:
O(knlogk)
,其中k为链表数,n为某个链表的最大节点数。我们最多会遍历kn个节点,而每次遍历维护有序性的时间复杂度为O(logk)
class Solution {
public:
struct compare{//自定义比较器
bool operator()(ListNode* n1, ListNode* n2){
return n1->val > n2->val;
}
};
//采用自定义比较器,实现小顶堆,因为默认大顶堆
priority_queue <ListNode*, vector<ListNode*>, compare> q;
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto node: lists) {
if (node != nullptr)
q.push(node);
}
ListNode head, *tail = &head;
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f;
tail = tail->next;
if (f->next != nullptr)
q.push(f->next);
}
return head.next;
}
};
评论 |
0条评论