做教育机器网站,广东省建设行业统一身份认证平台,工体做网站的公司,黑帽seo论坛本文涉及知识点
堆 优先队列
LeetCode23. 合并 K 个升序链表
给你一个链表数组#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。 示例 1#xff1a; 输入#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出#…本文涉及知识点
堆 优先队列
LeetCode23. 合并 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 104 0 lists[i].length 500 -104 lists[i][j] 104 lists[i] 按 升序 排列 lists[i].length 的总和不超过 104
堆优先队列
n ∑ l i s t s [ i ] . l e n g t h \sum lists[i].length ∑lists[i].length 暴力做法将数据全部放到大根堆从链表尾部开始拼接。时间复杂度 O(nlogn) 进阶的做法 由于链表是有序的那新链表的新元素一定是旧链表没有处理的首元素。 用 小根堆存储 lists首元素的值和指针。 出栈 栈顶元素并加到新栈尾部。 如果栈顶元素的next非空则将next加到堆中。 时间复杂度O(nlogk)
代码
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {priority_queuepairint,ListNode*, vectorpairint, ListNode*, std::greater heap;for (auto p : lists) {if( nullptr p){continue;}heap.emplace(make_pair(p-val, p));}ListNode* head nullptr, *tail nullptr;while (heap.size()) {auto [val, p] heap.top();heap.pop();if (nullptr head) {head tail new ListNode(val);}else {tail-next new ListNode(val);tail tail-next;}if (nullptr ! p-next ) {p p-next;heap.emplace(make_pair(p-val, p));}}return head;}
};扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
