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

[leetcode hot 150]第二十三题,合并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

 这题虽然是困难题,但是思路很清晰,很好理解,主要借助最小堆,因为最小堆有着将最小的元素置为堆顶的性质,所以每次取最小值时将最小堆的头推出即可。

并且使用dummy作为结果的头结点返回。代码及思路如下:

  1. 创建最小堆
    • 使用 PriorityQueue 作为最小堆,并定义比较器来比较节点的值。
  2. 初始化最小堆
    • 遍历所有链表,将每个链表的头节点(如果不为空)加入最小堆。
  3. 创建结果链表
    • 使用一个哑节点(dummy node)来简化头节点的处理。
  4. 合并过程
    • 当最小堆不为空时,重复以下步骤:
      a. 从堆中取出值最小的节点。
      b. 将这个节点添加到结果链表的末尾。
      c. 如果这个节点还有下一个节点,将下一个节点加入堆中。
  5. 返回结果
    • 返回哑节点的下一个节点,即合并后链表的真正头节点。

 复杂度分析

  • 时间复杂度:O(N log K),其中 N 是所有节点的总数,K 是链表的数量。
    每个节点都会被加入和取出堆一次,每次堆操作的时间复杂度是 O(log K)。
  • 空间复杂度:O(K),优先队列中最多同时存在 K 个节点。
import java.util.Comparator;
import java.util.PriorityQueue;public class no_23 {public static void main(String[] args) {ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));ListNode l3 = new ListNode(2, new ListNode(6));ListNode[] lists = {l1, l2, l3};// 合并链表ListNode result = mergeKLists(lists);// 打印结果while (result != null) {System.out.print(result.val + " ");result = result.next;}}public static ListNode mergeKLists(ListNode[] lists) {//  最小堆PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));//  将所有的链表头节点加入最小堆for (ListNode head : lists) {if (head != null) {minHeap.offer(head);}}ListNode dummy = new ListNode(0);ListNode tail = dummy;while (!minHeap.isEmpty()) {ListNode node = minHeap.poll();tail.next = node;tail = tail.next;if (node.next != null) {minHeap.offer(node.next);}}return dummy.next;}
}
class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

相关文章:

[leetcode hot 150]第二十三题,合并K个升序链表

题目&#xff1a; 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 1&#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 解释&#xff1a…...

MybatisPlus实现插入/修改数据自动设置时间

引言 插入数据时自动设置当前时间&#xff0c;更新数据时自动修改日期为修改时的日期。 使用MybatisPlus的扩展接口MetaObjectHandler 步骤 实现接口 实体类加注解 实现接口 package com.example.vueelementson.common;import com.baomidou.mybatisplus.core.handlers.M…...

Java语言程序设计篇一

Java语言概述 Java语言起源编程语言最新排名名字起源Java语言发展历程Java语言的特点Java虚拟机垃圾回收Java语言规范Java技术简介Java程序的结构Java程序注意事项&#xff1a;注释编程风格练习 Java语言起源 1990年Sun公司提出一项绿色计划。1992年语言开发成功最初取名为Oak…...

Calicoctl工具学习 —— 筑梦之路

官方文档&#xff1a; Calico Documentation | Calico Documentation 插件方式安装 calicoctl 工具 curl -o kubectl-calico -O -L "https://github.com/projectcalico/calicoctl/releases/download/v3.20.0/calicoctl"cp kubectl-calico /usr/bin/kubectl-calic…...

Wormhole Filters: Caching Your Hash on Persistent Memory——泛读笔记

EuroSys 2024 Paper 论文阅读笔记整理 问题 近似成员关系查询&#xff08;AMQ&#xff09;数据结构可以高效地近似确定元素是否在集合中&#xff0c;例如Bloom滤波器[10]、cuckoo滤波器[23]、quotient滤波器[8]及其变体。但AMQ数据结构的内存消耗随着数据规模的增长而快速增长…...

PyTorch学习之torch.transpose函数

PyTorch学习之torch.transpose函数 一、简介 torch.transpose 函数我们用于交换张量的维度。 二、语法 torch.transpose 函数用于交换给定张量的两个维度&#xff0c;其语法如下&#xff1a; torch.transpose(input, dim0, dim1)三、参数 input&#xff1a;待交换维度的张…...

Git仓库介绍

1. Github GitHub 本身是一个基于云端的代码托管平台&#xff0c;它提供的是远程服务&#xff0c;而不是一个可以安装在本地局域网的应用程序。因此&#xff0c;GitHub 不可以直接在本地局域网进行安装。 简介&#xff1a;GitHub是最流行的代码托管平台&#xff0c;提供了大量…...

人工智能笔记分享

文章目录 人工智能图灵测试分类分类与聚类的区别&#xff08;重点&#xff09;分类 (Classification)聚类 (Clustering) 特征提取 分类器&#xff08;重点&#xff09;特征提取为什么要进行特征提取&#xff1f;&#xff08;重点&#xff09;分类器 训练集、测试集大小&#x…...

秋招提前批面试经验分享(上)

⭐️感谢点开文章&#x1f44b;&#xff0c;欢迎来到我的微信公众号&#xff01;我是恒心&#x1f60a; 一位热爱技术分享的博主。如果觉得本文能帮到您&#xff0c;劳烦点个赞、在看支持一下哈&#x1f44d;&#xff01; ⭐️我叫恒心&#xff0c;一名喜欢书写博客的研究生在读…...

[AIGC] ClickHouse的表引擎介绍

ClickHouse是一种高性能的列式数据库管理系统&#xff0c;支持各种不同的表引擎。表引擎是数据库系统中的核心组件&#xff0c;它定义了数据的存储方式和访问方式。本文将介绍ClickHouse中常见的表引擎及其特点。 文章目录 一、MergeTree引擎二、ReplacingMergeTree引擎三、Sum…...

关于新装Centos7无法使用yum下载的解决办法

起因 之前也写了一篇类似的文章&#xff0c;但感觉有漏洞&#xff0c;这次想直接把漏洞补齐。 问题描述 在我们新装的Centos7中&#xff0c;如果想要用C编程&#xff0c;那就必须要用到yum下载&#xff0c;但是&#xff0c;很多新手&#xff0c;包括我使用yum下载就会遇到一…...

OpenEarthMap:全球高分辨率土地覆盖制图的基准数据集(开源来下载!!!)

OpenEarthMap由220万段5000张航拍和卫星图像组成&#xff0c;覆盖6大洲44个国家97个地区&#xff0c;在0.25-0.5m的地面采样距离上人工标注8类土地覆盖标签。我们提供8类标注:裸地、牧场、已开发空间、道路、树木、水、农业用地和建筑。类选择与现有的具有亚米GSD的产品和基准数…...

工作助手VB开发笔记(1)

1.思路 1.1 样式 样式为常驻前台的一个小窗口&#xff0c;小窗口上有三到四个按钮&#xff0c;为一级功能&#xff0c;是当前工作内容的常用功能窗口&#xff0c;有十个二级窗口&#xff0c;为选中窗口时的扩展选项&#xff0c;有若干后台功能&#xff0c;可选中至前台 可最…...

WAWA鱼曲折的大学四年回忆录

声明&#xff1a;本文内容纯属个人主观臆断&#xff0c;如与事实不符&#xff0c;请参考事实 前言&#xff1a; 早想写一下大学四年的总结了&#xff0c;但总是感觉无从下手&#xff0c;不知道从哪里开始写&#xff0c;通过这篇文章主要想做一个记录&#xff0c;并从现在的认…...

Go 依赖注入设计模式

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...

使用React复刻ThreeJS官网示例——keyframes动画

最近在看three.js相关的东西&#xff0c;想着学习一下threejs给的examples。源码是用html结合js写的&#xff0c;恰好最近也在学习react&#xff0c;就用react框架学习一下。 本文参考的是threeJs给的第一个示例 three.js examples (threejs.org) 一、下载threeJS源码 通常我们…...

嵌入式linux面试1

1. linux 1.1. Window系统和Linux系统的区别 linux区分大小写windows在dos&#xff08;磁盘操作系统&#xff09;界面命令下不区分大小写&#xff1b; 1.2. 文件格式区分 windows用扩展名区分文件&#xff1b;如.exe代表执行文件&#xff0c;.txt代表文本文件&#xff0c;.…...

智能交通(3)——Learning Phase Competition for Traffic Signal Control

论文分享 https://dl.acm.org/doi/pdf/10.1145/3357384.3357900https://dl.acm.org/doi/pdf/10.1145/3357384.3357900 论文代码 https://github.com/gjzheng93/frap-pubhttps://github.com/gjzheng93/frap-pub 摘要 越来越多可用的城市数据和先进的学习技术使人们能够提…...

【扩散模型】LCM LoRA:一个通用的Stable Diffusion加速模块

潜在一致性模型&#xff1a;[2310.04378] Latent Consistency Models: Synthesizing High-Resolution Images with Few-Step Inference (arxiv.org) 原文&#xff1a;Paper page - Latent Consistency Models: Synthesizing High-Resolution Images with Few-Step Inference (…...

【PYG】pytorch中size和shape有什么不同

一般使用tensor.shape打印维度信息&#xff0c;因为简单直接 在 PyTorch 中&#xff0c;size 和 shape 都用于获取张量的维度信息&#xff0c;但它们之间有细微的区别。下面是它们的定义和用法&#xff1a; size&#xff1a; size 是一个方法&#xff08;size()&#xff09;和…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...