如何合并多个升序链表?
前言
本文主要介绍如何将多个小的升序链表合并一个大的升序链表。
需求描述
给出K个升序链接,要求把这K个升序链表合并成一个,并且这个链表也是升序的。
例如:A = [1,5,6], B = [2,3,8], C = [4,4,9] 将这3个链表合并成一个链表D,合并后D = [1,2,3,4,4,5,6,8,9],并且将D的第一个节点返回。
思路解析
我们可以采用优先级队列来实现,先把每个链表的头结点放到一个优先级队列里,优先级队列也叫小根堆。
在放小根堆的时候,谁小就把谁放在最上面。需要注意的是,我们放入的时候,放入的是节点,所以通过这个节点是可以访问整个链表的。
我们看下处理过程:
- 首先把每个链接的头结点放入小根堆中:
1,2,4。 - 首先弹出最小的值:
1。 - 把
1节点的下一个节点5放入小根堆中,此时小根堆会自动调整顺序,此时为:2, 4, 5。 - 将
2节点弹出,让1节点的next指针指向2节点,并且将2节点的下一个节点6放入小根堆,此时已弹出的节点为1,2,而小根堆为4, 5, 6。 - 将
4节点弹出,让2节点的next指针指向4节点,并且将4节点的下一个节点4放入小根堆中,此时已弹出的节点为1,2,4,而小根堆为4, 5, 6。 - 依此类推,每弹出一个节点,拼接在已弹出节点的后面,并将弹出节点的下一个节点放入小根堆中,直到小根堆中所有的元素全部弹出。
好了,现在整体思路有了,但是现在是不是有个疑问?我们在做算法时,使用到了优先队列,那么我们可以使用系统自带的优先队列吗?
个人感觉,如果是面试时,这个系统自带的类只是题目中很小的一部分,比如上面的题目,主要考察的是如何实现这个过程,而不是考察如何实现优先队列的,如果没有特殊要求不让使用的话,是可以使用的。当然,如果考察是要实现一个优先队列,我要是直接new一个PriorityQueue,我估计面试官会一巴掌把我拍出来。
代码实现
链表节点定义如下:
public class ListNode {public int val;public ListNode next;
}
复制代码
因为是小根堆,需要一个排序算法,所以定义一个比较器如下:
public class ListNodeComparator implements Comparator<ListNode> {@Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val - o2.val; }
}
复制代码
合并链接:
public ListNode mergeKLists(ListNode[] lists) {if (lists == null) {return null;}PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());for (int i = 0; i < lists.length; i++) {if (lists[i] != null) {heap.add(lists[i]);}}if (heap.isEmpty()) {return null;}ListNode head = heap.poll();ListNode pre = head;if (pre.next != null) {heap.add(pre.next);}while (!heap.isEmpty()) {ListNode cur = heap.poll();pre.next = cur;pre = cur;if (cur.next != null) {heap.add(cur.next);}}return head;
}
复制代码
这个方法参数lists代表要传进来多少个链表,方法合并多个链表后,返回链表的第一个节点。
时间复杂度
假设有M个链表,M个链表的总节点个数为N。此时,对于小根堆来说,他的规模大小为M,则对于小根堆来说他的操作时间复杂度为O(logM),一共有N个节点,所以时间复杂度为O(N*logM)。
总结
本文主要介绍如何将多个小的升序链表合并一个大的升序链表,介绍了实现这个功能的思路分析,使用优先队列自动排序的特性实现了这个功能,当然这里我们使用的是系统自带的优先队列,其实也可以自己实现一个,个人感觉没太必要,就先偷个懒 ^_^
相关文章:
如何合并多个升序链表?
前言 本文主要介绍如何将多个小的升序链表合并一个大的升序链表。 需求描述 给出K个升序链接,要求把这K个升序链表合并成一个,并且这个链表也是升序的。 例如:A [1,5,6], B [2,3,8], C [4,4,9] 将这3个链表合并成一个链表D…...
23上半年信息系统项目管理师新老教程兼顾使用备考策略
在离考试仅有50多天的时候,软考办发文:“为方便报考信息系统项目管理师的考生进行复习备考,2023年上半年信息系统项目管理师考试第3版、第4版教程兼顾使用”。 其实软考办发布这样一条信息,也是为了照顾那些在新版发布以前按第…...
Linux环境搭建SVN服务器并实现公网访问 - cpolar端口映射
文章目录前言1. Ubuntu安装SVN服务2. 修改配置文件2.1 修改svnserve.conf文件2.2 修改passwd文件2.3 修改authz文件3. 启动svn服务4. 内网穿透4.1 安装cpolar内网穿透4.2 创建隧道映射本地端口5. 测试公网访问6. 配置固定公网TCP端口地址6.1 保留一个固定的公网TCP端口地址6.2 …...
仿牛客网社区Web开发项目代码逐行精读(更新中)
仿牛客网社区Web开发项目怎么看项目?如何调试项目前瞻技术架构项目亮点开始看代码LoginControllerDiscussPostController怎么看项目? pom.xml看技术架构resource看配置文件,这个项目是前后端不分离的以调试为导向,从前端入手检查…...
5G NR调制阶数与EVM关系以及对系统SNR要求分析
移动通信技术对数据传输速率要求越来越高。一种提高传输速率的思路是使用更高阶的QAM 调制方式,例如5G NR 的256QAM PDSCH,微波的1024QAM,2048QAM和4096QAM 调制。更高阶的QAM 调制方式对系统也提出了更高的要求。例如某个系统的EVM 测试结果…...
【NAS群晖drive异地访问】远程连接drive挂载电脑硬盘「内网穿透」
文章目录前言1.群晖Synology Drive套件的安装1.1 安装Synology Drive套件1.2 设置Synology Drive套件1.3 局域网内电脑测试和使用2.使用cpolar远程访问内网Synology Drive2.1 Cpolar云端设置2.2 Cpolar本地设置2.3 测试和使用3. 结语转发自CSDN远程穿透的文章:【群晖…...
react:hooks为什么不能写在条件语句里
背景 最近朋友在面试,说面试官问到了一个问题不会,说为什么 react hooks为什么不能写在条件语句里,今天我们来研究一下这个问题。 我们在来简单实现一个 useState: const reRender () > {stateIndex -1 ReactDOM.render(&…...
模型优势缺陷整理
(1)BERT 1. 计算资源消耗:bert模型是一个相对较大的模型,具有数亿个参数。因此,为了训练和使用bert模型,需要大量的计算资源和时间。 2. 学习不足问题:尽管bert模型在大规模语料库上进行了预训…...
编写猫咪相册应用 HTML
文章目录1. 标题元素标签2. p元素用于在网站上创建一段文本3. 注释4. 页面主要部分标识标签5. 通过使用img元素来为你的网站添加图片6. 使用锚点元素(a)链接到另一个页面7. 使用 section 元素将照片内容与未来的内容分开8. 无序列表(ul)元素,列表项(li)元素在列表中…...
基于Arduino与LabVIEW的远程家庭监控系统
在基于Arduino与LabVIEW的远程家庭监控系统中,Arduino Uno控制器需要完成以下功能:1)通过W5100网络模块接收并判断命令,采集和传输温度、煤气浓度、热释电传感器的数据,并通过W5100网络模块上传给LabVIEW软件。2&#…...
使用FRP(快速反向代理)实现内网穿透——以腾讯云服务器为例
一、FRP简介 FRP,即快速反向代理技术(fast reverse proxy)。本文的FRP程序是基于github开源项目GitHub - fatedier/frp。当前,该程序可实现:“将位于 NAT 或防火墙后面的本地服务器暴露给互联网”。它目前支持 TCP 和…...
d跨语言链接优化
原文 使用LDC的(LTO)链接时优化的简短文章,包含演示了如何提高程序性能的简单示例.因为LTO在LLVMIR级别工作,因此可跨越C/D语言优化! 重要提示:LDC/LLVM的LTO在窗口上不可用. 链接时优化 (LTO)链接时优化是指链接时的程序优化.链接器提取所有目标文件在一起,并合并到一个程序…...
【Linux】-- 进程概念的引入
目录 硬件 冯诺依曼体系结构 冯诺依曼体系结构推导 重点概念 网络数据流向 软件 操作系统(Operator System - OS) 概念 定位 进程内核数据结构PCB(task_struct) 通过系统调用创建进程-fork初始 fork基本用法 使用if进行分流 查看运行效果 …...
一文看懂“低代码、零代码”是什么?有什么区别?
低代码和零代码近几年热度一直居高不下,乍一看,很容易混淆低代码和零代码开发平台—— 因为它们都是传统开发的替代方案,旨在通过类似于可视化编程的功能加速软件开发过程。 但二者根本不是一回事。从开发人员经验 、目标角色到使用场景&…...
【华为OD机试真题】去除多余的空格(java)
去除多余空格 知识点字符串数组Q队列时间限制:2s空间限制:256MB限定语言:不限 题目描述: 去除文本多余空格,但不去除配对单引号之间的多余空格。给出关键词的起始和结束 下标,去除多余空格后刷新关键词的起始和结束下标。 输入: Life is painting a picture, not …...
【SQL 必知必会】- 第十三课 创建高级联结
目录 使用表别名 Oracle 中没有AS 使用不同类型的联结 自联结 用自联结而不用子查询 自然联结 外联结 全外联结 使用带聚集函数的联结 使用联结和联结条件 使用表别名 SQL 除了可以对列名和计算字段使用别名,还允许给表名起别名。这样做有两个主要理由ÿ…...
ios逆向工具有那些
以下是一些常用的 iOS 逆向工具: Cycript:一种用于在运行时动态分析和修改 iOS 应用程序的强大工具,可以与应用程序进行交互式调试和注入代码。 Frida:一个强大的动态二进制插桩工具,可以在运行时修改应用程序的行为&…...
【软件设计师14】UML建模
UML建模 稳定出一个,但是由于UML的图比较多,所以这种题比数据流图和数据库难度高 一般都会考用例图和类图,再附加其他的图 1. 用例图 包含关系include:比如登记外借信息必须先有用户登录 扩展关系extend:修改书籍…...
容器镜像的设计原理
1 概述: 1.1 历史概要 2016年,Docker制定了镜像规范v2,并在Docker 1.10中实现了这个规范。镜像规范v2分为Schema 1和Schema 2。 Schema 1主要兼容使用v1规范的Docker客户端(从2017年2月起,镜像规范v1不再被Registry支…...
arm64异常向量表
arm64异常向量表1 arm64异常向量表2 linux arm64异常向量表3 kernel_ventry宏4 异常向量表的保存4. VBAR_ELx寄存器4.2 __primary_switched4.3 __primary_switched1 arm64异常向量表 When an exception occurs, the processor must execute handler code which corresponds to …...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
