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

Java实现K个排序链表的高效合并:逐一合并、分治法与优先队列详解

Java实现K个排序链表的高效合并:逐一合并、分治法与优先队列详解

在算法和数据结构的学习中,链表是一个非常基础但又极具挑战的数据结构。尤其是当面对合并多个排序链表的问题时,如何在保证效率的前提下实现代码的简洁与高效,往往是算法设计的关键。本文将详细探讨如何使用Java中的优先队列(PriorityQueue)来实现K个排序链表的高效合并,并为常用的解决方案提供示例代码。

1. 问题背景

在这个问题中,我们有K个已经排序的链表,目标是将这些链表合并成一个新的排序链表,并返回合并后的链表头节点。简单的例子如下:

  • 链表1:1 -> 4 -> 5
  • 链表2:1 -> 3 -> 4
  • 链表3:2 -> 6

合并后的链表为:1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

这个问题的难点在于如何高效地处理K个链表的合并。以下是三种常用的解决方案。

2. 常用解决方案
  1. 逐一合并法

逐一合并法的思路是依次合并两个链表,最终得到结果链表。虽然这种方法简单易懂,但其时间复杂度较高,尤其是在链表数量较多的情况下。

示例代码:

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}public class MergeKListsSequentially {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode tail = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {tail.next = l1;l1 = l1.next;} else {tail.next = l2;l2 = l2.next;}tail = tail.next;}tail.next = (l1 != null) ? l1 : l2;return dummy.next;}public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) {return null;}ListNode mergedList = lists[0];for (int i = 1; i < lists.length; i++) {mergedList = mergeTwoLists(mergedList, lists[i]);}return mergedList;}public static void main(String[] args) {ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));ListNode list3 = new ListNode(2, new ListNode(6));ListNode[] lists = new ListNode[]{list1, list2, list3};MergeKListsSequentially solution = new MergeKListsSequentially();ListNode mergedList = solution.mergeKLists(lists);while (mergedList != null) {System.out.print(mergedList.val + " ");mergedList = mergedList.next;}}
}

解释

  • 通过mergeTwoLists方法,将两个有序链表合并成一个新的有序链表。
  • mergeKLists方法中,通过循环依次合并所有链表。

时间复杂度
最坏情况下为O(KN),其中K是链表的数量,N是每个链表的平均长度。

  1. 分治法

分治法是一种更高效的解决方案,通过递归地将链表分成两部分,分别进行合并,最终得到完整的合并链表。

示例代码:

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}public class MergeKListsDivideAndConquer {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode tail = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {tail.next = l1;l1 = l1.next;} else {tail.next = l2;l2 = l2.next;}tail = tail.next;}tail.next = (l1 != null) ? l1 : l2;return dummy.next;}public ListNode mergeKLists(ListNode[] lists, int start, int end) {if (start == end) {return lists[start];}int mid = start + (end - start) / 2;ListNode left = mergeKLists(lists, start, mid);ListNode right = mergeKLists(lists, mid + 1, end);return mergeTwoLists(left, right);}public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) {return null;}return mergeKLists(lists, 0, lists.length - 1);}public static void main(String[] args) {ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));ListNode list3 = new ListNode(2, new ListNode(6));ListNode[] lists = new ListNode[]{list1, list2, list3};MergeKListsDivideAndConquer solution = new MergeKListsDivideAndConquer();ListNode mergedList = solution.mergeKLists(lists);while (mergedList != null) {System.out.print(mergedList.val + " ");mergedList = mergedList.next;}}
}

解释

  • mergeKLists方法通过分治的方式递归地将链表两两合并,最终得到合并的结果链表。

时间复杂度
时间复杂度为O(N log K),其中N是所有节点的总数,K是链表的数量。

  1. 优先队列法

使用优先队列可以更加高效地解决问题。优先队列可以自动维护一个有序的队列,确保每次取出最小的节点,进行合并。

示例代码

import java.util.PriorityQueue;class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}public class MergeKListsUsingPriorityQueue {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);// 将每个链表的头节点加入优先队列for (ListNode list : lists) {if (list != null) {queue.add(list);}}// 创建虚拟头节点ListNode dummy = new ListNode(0);ListNode tail = dummy;// 逐步处理优先队列中的节点while (!queue.isEmpty()) {ListNode minNode = queue.poll();tail.next = minNode;tail = tail.next;// 如果最小节点的下一个节点不为空,继续加入优先队列if (minNode.next != null) {queue.add(minNode.next);}}// 防止链表成环,尾节点指向nulltail.next = null;return dummy.next;}public static void main(String[] args) {ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));ListNode list3 = new ListNode(2, new ListNode(6));ListNode[] lists = new ListNode[]{list1, list2, list3};MergeKListsUsingPriorityQueue solution = new MergeKListsUsingPriorityQueue();ListNode mergedList = solution.mergeKLists(lists);while (mergedList != null) {System.out.print(mergedList.val + " ");mergedList = mergedList.next;}}
}

解释

  • mergeKLists方法使用优先队列存储每个链表的头节点,并逐步处理优先队列中的最小节点,确保合并后的链表依然有序。

时间复杂度
时间复杂度为O(N log K),其中N是所有节点的总数,K是链表的数量。
4. 优化
将每个链表的头节点插入优先队列,并通过逐步处理队列中的最小节点来维护链表的顺序。每次从队列中取出一个节点后,我们将该节点的下一个节点(如果存在)加入队列。这样可以减少优先队列的操作次数,从而提高效率。
示例代码

import java.util.PriorityQueue;class MergeKSortedListsOptimized {public ListNode mergeKLists1(ListNode[] lists) {// 创建一个最小堆优先队列,根据节点的值进行排序PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);// 遍历所有链表for (ListNode list : lists) {// 如果链表不为空if (list != null) {// 将链表头节点加入优先队列queue.add(list);}}// 创建一个虚拟头节点ListNode dummy = new ListNode(0);// 尾节点指向虚拟头节点ListNode tail = dummy;// 当优先队列不为空时while (!queue.isEmpty()) {// 从优先队列中取出最小的节点ListNode minNode = queue.poll();// 将最小节点连接到当前链表的末尾tail.next = minNode;// 更新尾节点为当前最小节点tail = tail.next;// 如果最小节点还有下一个节点if (minNode.next != null) {// 将最小节点的下一个节点加入优先队列queue.add(minNode.next);}}// 将尾节点的next指针置为null,表示链表结束tail.next = null;// 返回合并后的链表的头节点(虚拟头节点的下一个节点)return dummy.next;}
}

解释
该实现与前一个方法类似,但不同的是我们只将链表的头节点加入优先队列,然后逐个处理节点。在处理每个节点时,如果它有下一个节点,我们将下一个节点加入队列。这样做可以有效减少优先队列的操作次数,提高算法效率。

时间复杂度
时间复杂度为 O(N * log(K)),其中 K 是链表的数量,N 是所有链表中节点的总数。

4. 总结

通过以上三种常用的解决方案,我们可以清楚地看到,不同的方法在时间复杂度和实现复杂度上的权衡。对于链表数量较少的情况,逐一合并法可能更简单易行;而在链表数量较多时,分治法和优先队列法则可以更高效地解决问题。在实际开发中,优先队列法常常是首选,因为它在效率和实现上都表现得十分优秀。

相关文章:

Java实现K个排序链表的高效合并:逐一合并、分治法与优先队列详解

Java实现K个排序链表的高效合并&#xff1a;逐一合并、分治法与优先队列详解 在算法和数据结构的学习中&#xff0c;链表是一个非常基础但又极具挑战的数据结构。尤其是当面对合并多个排序链表的问题时&#xff0c;如何在保证效率的前提下实现代码的简洁与高效&#xff0c;往往…...

Xinstall揭秘:高效App推广背后的黑科技

在移动互联网时代&#xff0c;App的运营推广成为了开发者们最为关注的话题之一。然而&#xff0c;随着市场竞争的加剧&#xff0c;推广难度也越来越大。这时候&#xff0c;一款名为Xinstall的品牌走进了我们的视线&#xff0c;它以其独特的技术和解决方案&#xff0c;为App推广…...

星巴克VS瑞幸,新王、旧王之争给新CEO带来哪些启示

“变化是生命的元素&#xff0c;求变是生命的力量”&#xff0c;马克吐温曾这样解释生命。而商场上何尝不是如此&#xff0c;正因为世异则事异&#xff0c;求变也是企业的常态。 近日&#xff0c;星巴克官宣布莱恩尼科尔(Brian Niccol)将于9月9日接替拉什曼纳拉辛汉(Laxman Na…...

C语言 | Leetcode C语言题解之第354题俄罗斯套娃信封问题

题目&#xff1a; 题解&#xff1a; int cmp(int** a, int** b) {return (*a)[0] (*b)[0] ? (*b)[1] - (*a)[1] : (*a)[0] - (*b)[0]; }int maxEnvelopes(int** envelopes, int envelopesSize, int* envelopesColSize) {if (envelopesSize 0) {return 0;}qsort(envelopes, …...

大型俄罗斯国际展览会介绍

今天分享一些在俄罗斯比较知名的国际展览会&#xff0c;以下展会大多为一年一届&#xff0c;具体展出时间大家可去网上查询了解&#xff0c;充分利用合适的展会&#xff0c;无疑是企业拓展市场、塑造品牌、对接资源、紧跟行业趋势的重要途径。 1、俄罗斯国际食品展览会 展览地…...

CST软件仿真案例:圆极化平板天线仿真02

本期继续完成一款圆极化Patch天线的仿真实例。读者可以完整的了解到怎么用CST微波工作室&#xff0c;完成对一款天线建模、设置到仿真分析的完整过程。 本期中&#xff0c;我们要设计的圆极化天线尺寸如下图所示&#xff1a; 本期内容是接着上期部分开始。首先先完成仿真实例0…...

【前端】vue监视属性和计算属性对比

首先分开讲解各个属性的作用。 1.计算属性 作用&#xff1a;用来计算出来一个值&#xff0c;这个值调用的时候不需要加括号&#xff0c;会根据依赖进行缓存&#xff0c;依赖不变&#xff0c;computed的值不会重新计算。 const vm new Vue({el:#root,data:{lastName:张,firstNa…...

探索提示工程 Prompt Engineering的奥妙

一、探索提示工程 Prompt Engineering 1. 介绍通用人工智能和专用人工智能 人工智能&#xff08;AI&#xff09;可以分为通用人工智能&#xff08;AGI&#xff09;和专用人工智能&#xff08;Narrow AI&#xff09;。AGI是一种能够理解、学习和执行任何人类可以完成的任务的智…...

算法阶段总结1

阶段总结 通过今天晚上的这场div2我深刻的意识到&#xff0c;光是会找窍门是远远不够的&#xff0c;你得会基础的建图&#xff0c;dp&#xff0c;高级数据结构&#xff0c;你这样才可以不断的提升自己&#xff0c;不可以一直在一个阶段停留下去&#xff0c;构造题可以刷下去&a…...

前端宝典之七:React性能优化实战精华篇

本文主要讲解实战项目中React性能优化的方法&#xff0c;主要分为三个大的方面&#xff1a;减少不必要的组件更新、组件优化以及tree-shaking&#xff0c;共11个方法 一、减少不必要组件更新 以下是一些可以避免在 React 提交阶段进行不必要重新渲染的方法&#xff1a; 1、使…...

【Dash】feffery_antd_components 简单入门示例

一、简单了解 feffery_antd_components 简称 fac &#xff0c;是一个基于 Ant Design 的 Dash 第三方组件&#xff0c;由Feffery 老师开源维护的 Python 网页开发组件库&#xff0c;它具有丰富的页面常用交互组件功能&#xff0c;使开发者可以使用纯Python的方式快速构建现代…...

JAVA学习-练习试用Java实现“路径交叉”

问题&#xff1a; 给定一个整数数组 distance 。从 X-Y 平面上的点 (0,0) 开始&#xff0c;先向北移动 distance[0] 米&#xff0c;然后向西移动 distance[1] 米&#xff0c;向南移动 distance[2] 米&#xff0c;向东移动 distance[3] 米&#xff0c;持续移动。也就是说&#…...

element组件封装

1.上传组件 <!--文件上传组件--> <template><div class"upload-file"><el-uploadref"fileUpload"v-if"props.type default":action"baseURL other.adaptationUrl(props.uploadFileUrl)":before-upload"h…...

Mysql (面试篇)

目录 唯一索引比普通索引快吗 MySQL由哪些部分组成&#xff0c;分别用来做什么 MySQL查询缓存有什么弊端&#xff0c;应该什么情况下使用&#xff0c;8.0版本对查询缓存由上面变更 MyISAM和InnoDB的区别有哪些 MySQL怎么恢复半个月前的数据 MySQL事务的隔离级别&#xff…...

【python】深入探讨python中的抽象类,创建、实现方法以及应用实战

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

微前端传值

在微前端架构中&#xff0c;不同子应用之间通过 postMessage 进行通信是一种常见的做法。这种方式允许不同源的窗口之间进行安全的信息交换。 下面是如何使用 postMessage 在微前端环境中发送和接收消息的示例。 步骤 1: 发送消息 假设您有一个主应用&#xff08;host app&a…...

《学会 SpringBoot · 依赖管理机制》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…...

全网行为管理软件有哪些?5款总有一款适合你的企业!

如今企业越来越依赖互联网进行日常运营和业务发展&#xff0c;网络行为管理变得日益重要。 为了确保网络安全、提高员工工作效率、避免敏感信息外泄等问题&#xff0c;企业往往需要借助全网行为管理软件来监控和管理内部网络的使用情况。 本文将为您介绍五款热门的全网行为管理…...

以简单的例子从头开始建spring boot web多模块项目(二)-mybatis简单集成

继续使用以简单的例子从头开始建spring boot web多模块项目&#xff08;一&#xff09;中的项目进行mybatis集成。 1、pom.xml文件中&#xff0c;增加相关的依赖包的引入&#xff0c;分别是mybatis-spring-boot-starter、lombok、mysql-connector-java 如下&#xff1a; <d…...

Golang | Leetcode Golang题解之第354题俄罗斯套娃信封问题

题目&#xff1a; 题解&#xff1a; func maxEnvelopes(envelopes [][]int) int {n : len(envelopes)if n 0 {return 0}sort.Slice(envelopes, func(i, j int) bool {a, b : envelopes[i], envelopes[j]return a[0] < b[0] || a[0] b[0] && a[1] > b[1]})f : …...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...