[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作为结果的头结点返回。代码及思路如下:
- 创建最小堆:
- 使用
PriorityQueue作为最小堆,并定义比较器来比较节点的值。- 初始化最小堆:
- 遍历所有链表,将每个链表的头节点(如果不为空)加入最小堆。
- 创建结果链表:
- 使用一个哑节点(dummy node)来简化头节点的处理。
- 合并过程:
- 当最小堆不为空时,重复以下步骤:
a. 从堆中取出值最小的节点。
b. 将这个节点添加到结果链表的末尾。
c. 如果这个节点还有下一个节点,将下一个节点加入堆中。- 返回结果:
- 返回哑节点的下一个节点,即合并后链表的真正头节点。
复杂度分析
- 时间复杂度: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个升序链表
题目: 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 输入:lists [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:…...
MybatisPlus实现插入/修改数据自动设置时间
引言 插入数据时自动设置当前时间,更新数据时自动修改日期为修改时的日期。 使用MybatisPlus的扩展接口MetaObjectHandler 步骤 实现接口 实体类加注解 实现接口 package com.example.vueelementson.common;import com.baomidou.mybatisplus.core.handlers.M…...
Java语言程序设计篇一
Java语言概述 Java语言起源编程语言最新排名名字起源Java语言发展历程Java语言的特点Java虚拟机垃圾回收Java语言规范Java技术简介Java程序的结构Java程序注意事项:注释编程风格练习 Java语言起源 1990年Sun公司提出一项绿色计划。1992年语言开发成功最初取名为Oak…...
Calicoctl工具学习 —— 筑梦之路
官方文档: 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 论文阅读笔记整理 问题 近似成员关系查询(AMQ)数据结构可以高效地近似确定元素是否在集合中,例如Bloom滤波器[10]、cuckoo滤波器[23]、quotient滤波器[8]及其变体。但AMQ数据结构的内存消耗随着数据规模的增长而快速增长…...
PyTorch学习之torch.transpose函数
PyTorch学习之torch.transpose函数 一、简介 torch.transpose 函数我们用于交换张量的维度。 二、语法 torch.transpose 函数用于交换给定张量的两个维度,其语法如下: torch.transpose(input, dim0, dim1)三、参数 input:待交换维度的张…...
Git仓库介绍
1. Github GitHub 本身是一个基于云端的代码托管平台,它提供的是远程服务,而不是一个可以安装在本地局域网的应用程序。因此,GitHub 不可以直接在本地局域网进行安装。 简介:GitHub是最流行的代码托管平台,提供了大量…...
人工智能笔记分享
文章目录 人工智能图灵测试分类分类与聚类的区别(重点)分类 (Classification)聚类 (Clustering) 特征提取 分类器(重点)特征提取为什么要进行特征提取?(重点)分类器 训练集、测试集大小&#x…...
秋招提前批面试经验分享(上)
⭐️感谢点开文章👋,欢迎来到我的微信公众号!我是恒心😊 一位热爱技术分享的博主。如果觉得本文能帮到您,劳烦点个赞、在看支持一下哈👍! ⭐️我叫恒心,一名喜欢书写博客的研究生在读…...
[AIGC] ClickHouse的表引擎介绍
ClickHouse是一种高性能的列式数据库管理系统,支持各种不同的表引擎。表引擎是数据库系统中的核心组件,它定义了数据的存储方式和访问方式。本文将介绍ClickHouse中常见的表引擎及其特点。 文章目录 一、MergeTree引擎二、ReplacingMergeTree引擎三、Sum…...
关于新装Centos7无法使用yum下载的解决办法
起因 之前也写了一篇类似的文章,但感觉有漏洞,这次想直接把漏洞补齐。 问题描述 在我们新装的Centos7中,如果想要用C编程,那就必须要用到yum下载,但是,很多新手,包括我使用yum下载就会遇到一…...
OpenEarthMap:全球高分辨率土地覆盖制图的基准数据集(开源来下载!!!)
OpenEarthMap由220万段5000张航拍和卫星图像组成,覆盖6大洲44个国家97个地区,在0.25-0.5m的地面采样距离上人工标注8类土地覆盖标签。我们提供8类标注:裸地、牧场、已开发空间、道路、树木、水、农业用地和建筑。类选择与现有的具有亚米GSD的产品和基准数…...
工作助手VB开发笔记(1)
1.思路 1.1 样式 样式为常驻前台的一个小窗口,小窗口上有三到四个按钮,为一级功能,是当前工作内容的常用功能窗口,有十个二级窗口,为选中窗口时的扩展选项,有若干后台功能,可选中至前台 可最…...
WAWA鱼曲折的大学四年回忆录
声明:本文内容纯属个人主观臆断,如与事实不符,请参考事实 前言: 早想写一下大学四年的总结了,但总是感觉无从下手,不知道从哪里开始写,通过这篇文章主要想做一个记录,并从现在的认…...
Go 依赖注入设计模式
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...
使用React复刻ThreeJS官网示例——keyframes动画
最近在看three.js相关的东西,想着学习一下threejs给的examples。源码是用html结合js写的,恰好最近也在学习react,就用react框架学习一下。 本文参考的是threeJs给的第一个示例 three.js examples (threejs.org) 一、下载threeJS源码 通常我们…...
嵌入式linux面试1
1. linux 1.1. Window系统和Linux系统的区别 linux区分大小写windows在dos(磁盘操作系统)界面命令下不区分大小写; 1.2. 文件格式区分 windows用扩展名区分文件;如.exe代表执行文件,.txt代表文本文件,.…...
智能交通(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加速模块
潜在一致性模型:[2310.04378] Latent Consistency Models: Synthesizing High-Resolution Images with Few-Step Inference (arxiv.org) 原文:Paper page - Latent Consistency Models: Synthesizing High-Resolution Images with Few-Step Inference (…...
【PYG】pytorch中size和shape有什么不同
一般使用tensor.shape打印维度信息,因为简单直接 在 PyTorch 中,size 和 shape 都用于获取张量的维度信息,但它们之间有细微的区别。下面是它们的定义和用法: size: size 是一个方法(size())和…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
