当前位置: 首页 > 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;和…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...