【堆 优先队列】23. 合并 K 个升序链表

本文涉及知识点

堆 优先队列

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(vector<ListNode*>& lists) {priority_queue<pair<int,ListNode*>, vector<pair<int, 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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/368922.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基流科技:超算界的新星,Pre-A轮融资大获成功

基流科技:超算界的新星,Pre-A轮融资大获成功! 在科技的浪潮中,一颗新星正在冉冉升起——基流科技,一家开放算力网络提供商,以其革命性的技术在超算界引起了轰动。今年年初,基流科技完成了 Pre-A 轮融资,由光速光合领投,此前已获得奇绩创坛、微梦传媒等知名投资方的青…

mysql定时备份数据库

文章目录 核心目标思路具体方法一、编写脚本二、修改文件属性三、找一个mysqldump文件四、把.sh放到定时器里 其它&#xff1a;windows的脚本 核心目标 解决数据库定时备份的工作。centos环境。 思路 用centos的crontab定时执行脚本。 具体方法 一、编写脚本 编写backup_…

Kafka集群部署(手把手部署图文详细版)

1.1.1 部署zookpeer 在node02下载并解压zookeeper软件包 cd /usr/local wget https://archive.apache.org/dist/zookeeper/zookeeper-3.4.6/zookeeper-3.4.6.tar.gz 或者&#xff1a;scp cat192.168.28.100:/home/cat/zookeeper-3.4.6.tar.gz /tmp&#xff08;注意目录&#xf…

鸿蒙小案例-首选项工具类

一个简单的首选项工具类 主要提供方法 初始化 init()方法建议在EntryAbility-》onWindowStageCreate 方法中使用 没多少东西&#xff0c;放一下测试代码 import { PrefUtil } from ./PrefUtil; import { promptAction } from kit.ArkUI;Entry Component struct PrefIndex {St…

计算机的错误计算(二十一)

摘要 两个不相等数相减&#xff0c;差为0&#xff1a; ? 在计算机的错误计算&#xff08;十九&#xff09;中&#xff0c;高中生小明发现本应为0的算式结果不为0. 今天他又发现对本不为0的算式&#xff0c;计算机的输出为0. 在 Python 中计算 &#xff1a; 则输出为0. 若用 C…

@react-google-maps/api实现谷歌地图嵌入React项目中,并且做到点击地图任意一处,获得它的经纬度

1.第一步要加入项目package.json中或者直接yarn install它都可以 "react-google-maps/api": "^2.19.3",2.加入项目中 import AMapLoader from amap/amap-jsapi-loader;import React, { PureComponent } from react; import { GoogleMap, LoadScript, Mar…

RabbitMQ消息可靠性等机制详解(精细版三)

目录 七 RabbitMQ的其他操作 7.1 消息的可靠性(发送可靠) 7.1.1 confim机制(保证发送可靠) 7.1.2 Return机制(保证发送可靠) 7.1.3 编写配置文件 7.1.4 开启Confirm和Return 7.2 手动Ack(保证接收可靠) 7.2.1 添加配置文件 7.2.2 手动ack 7.3 避免消息重复消费 7.3.…

JAVA:文件防重设计指南

1、简述 在现代应用程序中&#xff0c;处理文件上传是一个常见的需求。为了保证文件存储的高效性和一致性&#xff0c;避免重复存储相同的文件是一个重要的优化点。本文将介绍一种基于哈希值的文件防重设计&#xff0c;并详细列出实现步骤。 2、设计原理 文件防重的基本思路…

如何使用 3D 建模库在 C# 中将 3DS 转换为 USDZ?

USDZ/USD是一种 3D 文件格式&#xff0c;被广泛用于跨平台共享 3D 资产。另一方面&#xff0c;3DS是另一种以块形式存储数据的 3D 文件格式。在某些情况下&#xff0c;您需要将3DS 文件转换为 USDZ/USD文件格式。因此&#xff0c;本篇博文介绍了一个功能丰富的3D 建模库&#x…

6月30日功能测试Day10

3.4.4拼团购测试点 功能位置&#xff1a;营销-----拼团购 后台优惠促销列表管理可以添加拼团&#xff0c;查看拼团活动&#xff0c;启动活动&#xff0c;编辑活动&#xff0c;删除活动。 可以查看拼团活动中已下单的订单以状态 需求分析 功能和添加拼团 商品拼团活动页 3…

【Sping Boot2】笔记

Spring Boot 2入门 如何创建一个Spring Boot的Web例子&#xff1f;1.如何创建一个Spring Boot项目1.1 使用Maven构建一个Spring Boot 2项目1.1.1创建Maven工程注&#xff1a;Maven项目结构&#xff1a; 1.1.2引入SpingBoot相关依赖依赖注意事项&#xff1a; 1.1.3创建主类1.1.4…

传统数据处理系统存在的问题

传统应用的数据系统架构设计时&#xff0c;应用直接访问数据库系统。当用户访问量增加时&#xff0c;数据库无法支撑日益增长的用户请求的负载&#xff0c;从而导致数据库服务器无法及时响应用户请求&#xff0c;出现超时的错误。 出现这种情况以后&#xff0c;在系统架构上就采…

【python】OpenCV—Nighttime Low Illumination Image Enhancement

文章目录 1 背景介绍2 代码实现3 原理分析4 效果展示5 附录np.ndindexnumpy.ravelnumpy.argsortcv2.detailEnhancecv2.edgePreservingFilter 1 背景介绍 学习参考来自&#xff1a;OpenCV基础&#xff08;24&#xff09;改善夜间图像的照明 源码&#xff1a; 链接&#xff1a…

Word “当前页“ 与 “前一页“ (含部分内容)间有大半页空白,删除空白方法

鼠标光标选中需要向上移的句子&#xff0c;右键点击“段落”&#xff0c;然后在跳出的窗口中按照“换行和分页”中的红色方框内取消勾选后&#xff0c;点击确定即可。

Python | Leetcode Python题解之第216题组合总和III

题目&#xff1a; 题解&#xff1a; class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:"""回溯法&#xff0c;对于当前k和n, 枚举元素"""def backtracking(k: int, n: int, ans: List[int]):if k 0 or n <…

《米小圈日记魔法》边看边学,轻松掌握写日记的魔法!

在当今充满数字化娱乐和信息快速变迁的时代&#xff0c;如何创新引导孩子们学习&#xff0c;特别是如何培养他们的写作能力&#xff0c;一直是家长和教育者们关注的焦点。今天就向大家推荐一部寓教于乐的动画片《米小圈日记魔法》&#xff0c;该系列动画通过其独特的故事情节和…

【Unity配置数据文件】ScriptableObject核心应用

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 专栏交流&#x1f9e7;&…

【Linux进程通信】共享内存

目录 共享内存函数 头文件 shmget ftok函数​ shmat shmdt shmctl 共享内存区是最快的IPC 形式。一旦这样的内存映射到共享它的进程的地址空间&#xff0c;这些进程间数据传递不再涉及到操作系统内核&#xff0c;换句话说是进程不再通过执行进入内核的系统调用来传递彼此的数据…

探索如何赋予对象迭代魔法,轻松实现非传统解构赋值的艺术

前言 今天下午在网上冲浪过程中看到这样一个问题 面试题&#xff1a;如何让 var [a, b] {a: 1, b: 2} 解构赋值成功&#xff1f; 据说是某大厂面试题&#xff0c;于是我学习了一下这个问题&#xff0c;写下这篇文章记录一下。 学习过程 要想解决这个问题首先要知道什么是解…

Qt:7.QWidget属性介绍(cursor属性-光标形状、font属性-控件文本样式、tooltip属性-控件提示信息)

目录 一、cursor属性-光标形状&#xff1a; 1.1cursor属性介绍&#xff1a; 1.2获取当前光标形状——cursor()&#xff1a; 1.3 设置光标的形状——setCursor()&#xff1a; 1.4 设置自定义图片为光标&#xff1a; 二、font属性-控件文本样式&#xff1a; 2.1font属性介绍…