如何合并多个升序链表?
前言
本文主要介绍如何将多个小的升序链表合并一个大的升序链表。
需求描述
给出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 …...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
