当前位置: 首页 > news >正文

【LeetCode】23. 合并 K 个升序链表

题目链接:23. 合并 K 个升序链表
题目描述:
在这里插入图片描述
数据范围:
在这里插入图片描述

**思考:**这题实际上就是合并两个有序列表的进阶版,只不过这里变成了合并K个,那么这里我们显然就知道,核心的合并两个有序列表的思路不变,剩下的重点处理就在于如何将这K个链表进行两两合并了,方式有很多,但效率不一,下面介绍几种易想到的思路:

方法一:顺序合并

顺序合并思路很简单,就是顺序地将这K个链表两两地进行合并。

代码:

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeKLists(lists []*ListNode) *ListNode {if len(lists) == 0 {return new(ListNode).Next}res := lists[0]lists = lists[1:]for _,list := range lists {res = mergeTwoLists(res,list)}return res
}
// 合并两个升序链表
func mergeTwoLists(l1 ,l2 *ListNode) *ListNode {head := new(ListNode)l := headfor ;l1 != nil && l2 != nil; {if l1.Val < l2.Val {l.Next = l1l1 = l1.Next}else {l.Next = l2l2 = l2.Next}l = l.Next}if l1 != nil {l.Next = l1}if l2 != nil {l.Next = l2}return head.Next
}

在这里插入图片描述

方法二、分治

顺序合并的效率并不高,这样做就类似于阻塞操作,合并前面的链表的时候,无关的链表啥事儿都干不了,因此,我们可以考虑进行分治,先递归地划分区间两两合并,最后再将总的合并起来。

代码:

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeKLists(lists []*ListNode) *ListNode {if len(lists) == 0 {return new(ListNode).Next}return merge(0,len(lists)-1,lists)
}func merge(l,r int,lists []*ListNode) *ListNode {if l > r {return nil}if l == r {return lists[l]}mid := (l+r)>>1return mergeTwoLists(merge(l,mid,lists),merge(mid+1,r,lists))
}func mergeTwoLists(l1 ,l2 *ListNode) *ListNode {head := new(ListNode)l := headfor ;l1 != nil && l2 != nil; {if l1.Val < l2.Val {l.Next = l1l1 = l1.Next}else {l.Next = l2l2 = l2.Next}l = l.Next}if l1 != nil {l.Next = l1}if l2 != nil {l.Next = l2}return head.Next
}

在这里插入图片描述

方法三、小根堆

看了下题解找出了不同的写法的,基本上用了小根堆(优先队列)的结构来实现的,思路就是初始时将每个链表的头结点加入到堆中,调整成为一个小根堆,那么堆顶结点一定是最小的。循环取堆中的元素,直到堆为空,注意,每次从堆中取出一个节点就需要将该节点从堆中移除,并将这个节点的下一个节点加入到堆中。

代码:

func mergeKLists(lists []*ListNode) *ListNode {h := hp{}for _, head := range lists {if head != nil {h = append(h, head)}}heap.Init(&h) // 初始化小根堆res := &ListNode{} // 哨兵节点,作为合并后链表头节点的前一个节点cur := res // 当前合并的链表位置,也就res链表末尾for len(h) > 0 {node := heap.Pop(&h).(*ListNode) // 取出堆顶元素if node.Next != nil { // 该节点的下一个节点不空,就再加入堆中heap.Push(&h, node.Next)}cur.Next = node // 记录到答案中cur = cur.Next // 准备合并下一个节点}return res.Next
}// golang中小根堆的实现
type hp []*ListNode
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val } // 最小堆
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x interface{}) {*h = append(*h, x.(*ListNode))}
func (h *hp) Pop() interface{} {n := len(*h)ans := (*h)[n-1] // n-1个元素就是堆顶元素*h = (*h)[:n-1]return ans
}

在这里插入图片描述
这种做法很容易能看出复杂度为O(n*logk),其中k是链表长度,而n是所有链表节点数之和,这里logk主要是k个链表加入到堆中,所以时间复杂度为logk。

相关文章:

【LeetCode】23. 合并 K 个升序链表

题目链接&#xff1a;23. 合并 K 个升序链表 题目描述&#xff1a; 数据范围&#xff1a; **思考&#xff1a;**这题实际上就是合并两个有序列表的进阶版&#xff0c;只不过这里变成了合并K个&#xff0c;那么这里我们显然就知道&#xff0c;核心的合并两个有序列表的思路不…...

2023年【熔化焊接与热切割】免费试题及熔化焊接与热切割考试总结

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 熔化焊接与热切割免费试题参考答案及熔化焊接与热切割考试试题解析是安全生产模拟考试一点通题库老师及熔化焊接与热切割操作证已考过的学员汇总&#xff0c;相对有效帮助熔化焊接与热切割考试总结学员顺利通过考试。…...

为什么要学中文编程?它能有哪些益处?免费版编程工具怎么下载?系统化的编程教程课程怎么学习

一、为什么要学习这个编程工具&#xff1f;能给自己带来什么益处&#xff1f; 1、不论在哪里上班&#xff0c;都不是铁饭碗&#xff1a;现在全球经济低迷&#xff0c;使得很多企业倒闭&#xff0c; 大到知名国企小到私营企业&#xff0c;大量裁员。任何人都无法保证自己现在的…...

数据分析实战 - 2 订单销售数据分析(pandas 进阶)

题目来源&#xff1a;和鲸社区的题目推荐&#xff1a; 刷题源链接&#xff08;用于直接fork运行 https://www.heywhale.com/mw/project/6527b5560259478972ea87ed 刷题准备 请依次运行这部分的代码&#xff08;下方4个代码块&#xff09;&#xff0c;完成刷题前的数据准备 …...

测试服务器端口是否开通,计算退休时间

本案例知识点 netstat -tuln | grep 80 nestat 目前主机打开的网络服务端口&#xff0c;-tuln目前主机启动的服务&#xff0c;如图 报错说参数太多&#xff0c;仔细检查发现if后的中括号内&#xff0c;变量少双引号导致&#xff0c;改完之后运行显示22,25端口开放&#xff0…...

Prometheus接入AlterManager配置企业微信告警(基于K8S环境部署)

文章目录 一、创建企业微信机器人二、配置AlterManager告警发送至企业微信三、Prometheus接入AlterManager配置四、部署PrometheusAlterManager(放到一个Pod中)五、测试告警 注意&#xff1a;请基于 PrometheusGrafana监控K8S集群(基于K8S环境部署)文章之上做本次实验。 一、创…...

11.1 Linux 设备树

一、什么是设备树&#xff1f; 设备树(Device Tree)&#xff0c;描述设备树的文件叫做 DTS(DeviceTree Source)&#xff0c;这个 DTS 文件采用树形结构描述板级设备&#xff0c;也就是开发板上的设备信息&#xff1a; 树的主干就是系统总线&#xff0c; IIC 控制器、 GPIO 控制…...

万宾科技管网水位监测助力智慧城市的排水系统

以往如果要了解城市地下排水管网的水位变化&#xff0c;需要依靠人工巡检或者排查的方式&#xff0c;这不仅加大了人员的工作量&#xff0c;而且也为市政府带来了更多的工作难题。比如人员监管监测不到位或无法远程监控等情况&#xff0c;都会降低市政府对排水管网的管理能力&a…...

Glide transform CircleCrop()圆图,Kotlin

Glide transform CircleCrop()圆图&#xff0c;Kotlin import android.os.Bundle import android.widget.ImageView import androidx.appcompat.app.AppCompatActivity import com.bumptech.glide.load.resource.bitmap.CircleCropclass MainActivity : AppCompatActivity() {o…...

从NetSuite Payment Link杂谈财务自动化、数字化转型

最近在进行信息化的理论学习&#xff0c;让我有机会跳开软件功能&#xff0c;用更加宏大的视野&#xff0c;来审视我们在哪里&#xff0c;我们要到哪去。 在过去20多年&#xff0c;我们的财务软件经历了电算化、网络化、目前处于自动化、智能化阶段。从NetSuite这几年的功能发…...

1.UML面向对象类图和关系

文章目录 4种静态结构图类图类的表示类与类之间的关系依赖关系(Dependency)关联关系(Association)聚合(Aggregation)组合(Composition)实现(Realization)继承/泛化(Inheritance/Generalization)常用的UML工具reference欢迎访问个人网络日志🌹🌹知行空间🌹🌹 4种静态结构…...

JAVA小说小程序系统是怎样开发的

随着移动互联网的普及&#xff0c;小说阅读已经成为人们休闲娱乐的重要方式之一。为了满足广大读者的需求&#xff0c;我们开发了一款基于JAVA编程语言的小说小程序系统。本系统旨在提供一种便捷、高效、有趣的阅读体验&#xff0c;让用户能够随时随地阅读最新、最热门的小说。…...

【深度学习】pytorch——Tensor(张量)详解

笔记为自我总结整理的学习笔记&#xff0c;若有错误欢迎指出哟~ pytorch——Tensor 简介创建Tensortorch.Tensor( )和torch.tensor( )的区别torch.Tensor( )torch.tensor( ) tensor可以是一个数&#xff08;标量&#xff09;、一维数组&#xff08;向量&#xff09;、二维数组&…...

装修服务预约小程序的内容如何

大小装修不断&#xff0c;市场中大小品牌也比较多&#xff0c;对需求客户来说&#xff0c;可以线下咨询也可以线上寻找品牌&#xff0c;总是可以找到满意的服务公司&#xff0c;而对装修公司来说如今线下流量匮乏&#xff0c;很多东西也难以通过线下方式承载&#xff0c;更需要…...

easypoi 导出Excel 使用总结

easypoi 导出Excel 导出Excel需要设置标题&#xff0c;且标题是多行&#xff0c;标题下面是列表头 设置表格标题 ExportParams headExportParams new ExportParams();StringBuilder buffer new StringBuilder("");buffer.append("1、课程名称&#xff1a;....…...

MySQL性能优化的最佳20条经验

概述 关于数据库的性能&#xff0c;这并不只是DBA才需要担心的事。当我们去设计数据库表结构&#xff0c;对操作数据库时(尤其是查表时的SQL语句)&#xff0c;我们都需要注意数据操作的性能。下面讲下MySQL性能优化的一些点。 1. 为查询缓存优化你的查询 大多数的MySQL服务器…...

【Liunx基础】之指令(一)

【Liunx基础】之指令&#xff08;一&#xff09; 1.ls指令2.pwd命令3.cd指令4.touch指令5.mkdir指令(重要)6.rmdir指令与rm指令&#xff08;重要&#xff09;7.man指令&#xff08;重要&#xff09;8.cp指令&#xff08;重要&#xff09; &#x1f4c3;博客主页&#xff1a; 小…...

jQuery案例专题

jQuery案例专题 本学期主要担任的课程是js和jQuery&#xff0c;感觉用到的有一些案例挺有意思的&#xff0c;就对其进行了一下整理。 目录&#xff1a; 电影院的幕帘特效 手风琴特效 星光闪烁 网页轮播图 1.电影院的幕帘特效代码如下 html <!DOCTYPE html > <html…...

【Linux】服务器间免登陆访问

准备两台服务器&#xff0c;服务器A&#xff0c;服务器B 在服务器A中实现免登陆服务器B 进入服务器A操作 进入目录/root/.ssh cd /root/.ssh秘钥对使用默认文件名 生成秘钥对&#xff0c;在输入秘钥文件时直接回车则会使用默认文件名&#xff1a;id_rsa ssh-keygen -t rsa…...

【信息安全原理】——IP及路由安全(学习笔记)

目录 &#x1f552; 1. IPv4协议及其安全性分析&#x1f552; 2. IPsec&#xff08;IP Security&#xff09;&#x1f558; 2.1 IPsec安全策略&#x1f564; 2.1.1 安全关联&#xff08;Security Association, SA&#xff09;&#x1f564; 2.1.2 安全策略&#xff08;Security…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...

npm安装electron下载太慢,导致报错

npm安装electron下载太慢&#xff0c;导致报错 背景 想学习electron框架做个桌面应用&#xff0c;卡在了安装依赖&#xff08;无语了&#xff09;。。。一开始以为node版本或者npm版本太低问题&#xff0c;调整版本后还是报错。偶尔执行install命令后&#xff0c;可以开始下载…...