力扣23. 合并 K 个升序链表(最小堆)

Problem: 23. 合并 K 个升序链表

文章目录

  • 题目描述
  • 思路及解法
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路及解法

1.创建虚拟头节点dummy并创建辅助指针p指向dummy;
2.创建最小堆minHeap将每个链表的头节点存入;
3.当minHeap不为空时每次让p指向从最小堆堆顶取出的节点node,若node -next != nullptr则将node -> next也添加到minHeap中;并让p指针后移,最后返回dummy -> next

复杂度

时间复杂度:

O ( n l o g k ) O(nlogk) O(nlogk);其中 n n n为总共的节点个数, k k k为链表的数量

空间复杂度:

O ( n ) O(n) O(n)

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * An object for comparison
 */
struct compare {
    bool operator() (const ListNode* a, const ListNode* b) {
        return a -> val > b -> val;
    }
};
class Solution {
public:
    /**
     * Merge K ordered linked lists using minimum heap
     *
     * @param lists Set of ordered linked lists
     * @return ListNode*
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        priority_queue<ListNode*, vector<ListNode*>, compare> minHeap;
        for (ListNode* head : lists) {
            if (head != nullptr) {
                minHeap.push(head);
            }
        }

        while (!minHeap.empty()) {
            ListNode* node = minHeap.top();
            minHeap.pop();
            p -> next = node;
            if (node -> next != nullptr) {
                minHeap.push(node -> next);
            }
            p = p -> next;
        }
        return dummy -> next;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/472470.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【小沐学AI】Google AI大模型的一点点学习(Python)

文章目录 1、Google AI简介1.1 Google AI Studio1.2 Bard1.3 PaLM1.4 Gemini1.5 Gemini API1.6 Vertex AI1.7 Gemma 2、Google AI开发2.1 快速入门2.1.1 配置开发环境2.1.2 列出所有模型2.1.3 从文本输入生成文本2.1.4 从图像和文本输入生成文本2.1.5 聊天对话 结语 1、Google …

Covalent Network(CQT)与 Celo 集成,推动 Web3 下一代现实资产解决方案的发展

Covalent Network&#xff08;CQT&#xff09;是一个统一的区块链 API 提供商&#xff0c;其已正式与 Celo 集成&#xff0c;Celo 是一个以移动优先的 EVM 兼容链。这一重要的里程碑旨在提升 Celo 生态系统中开发者的能力&#xff0c;通过授予他们访问关键链上数据的权限&#…

踏“时间”与“空间”前来探寻复杂度的奥妙(Java篇)

本篇会加入个人的所谓‘鱼式疯言’ ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人…

基于WTR096-28SS芯片方案的宠物喂食器实现智能化喂食功能

一、简介 本方案宠物喂食器采用了WTR096-28SS芯片方案来实现智能化的喂食功能。该方案结合了先进的技术和设计理念&#xff0c;提供了便捷、智能和个性化的宠物喂食解决方案。 该宠物喂食器具备定时、定量喂食功能&#xff0c;可以根据主人设定的时间和食物量&#xff0c;自动…

xercesc库保存XML功能实现

目录 一 参考链接 二 运行结果 三 代码 一 参考链接 DOM Programming Guide (apache.org) Xerces-c DOM XML文件的构造_xerces-c domimplementation-CSDN博客 Xerces-c库的使用-CSDN博客 二 运行结果 三 代码 #if 1//参考链接&#xff1a; https://blog.csdn.net/RGBMa…

HarmonyOS NEXT应用开发之SideBarContainer侧边栏淡入淡出动效实现案例

介绍 在2in1或平板上&#xff0c;群聊侧边栏是一种较为常用的功能&#xff0c;虽然HarmonyOS已经具备了基本的动效&#xff0c;但是部分情况下开发者可能有定制侧边栏动效的需求&#xff0c;本例主要介绍了如何基于显式动画实现侧边栏的淡入淡出动效。 效果图预览 使用说明&a…

【区间、栈】算法例题

目录 六、区间 48. 汇总区间 ① 49. 合并区间 ② 50. 插入区间 ② 51. 用最少数量的箭引爆气球 ② 七、栈 52. 有效的括号 ① 53. 简化路径 ② 54. 最小栈 ② 55. 逆波兰表达式求值 ② √- 56. 基本计算器 ③ 六、区间 48. 汇总区间 ① 给定一个 无重复元素 的 …

静态代理IP如何测试?

随着互联网的普及&#xff0c;越来越多的人开始使用动态IP进行上网。但是在某些情况下&#xff0c;我们可能需要使用静态IP进行测试或特定的网络设置。本文将介绍如何获取静态IP进行测试以及静态IP的优点。 一、如何获取静态IP进行测试&#xff1f; 1.联系ISP&#xff08;Int…

DM-达梦数据库实时主备搭建

dm实时主备说明 将主库产生的 Redo日志传输到备库&#xff0c;备库接收并重演Redo日志&#xff0c;从而实现备库与主库的数据同步。 一、环境准备 1.1、配置环境准备 首先搭建实时主备&#xff0c;要规划好机器的&#xff0c;我准备两台机器服务器 主服务器 mast…

7-5 表格输出

题目链接&#xff1a;7-5 表格输出 一. 题目 1. 题目 2. 输入输出格式 3. 限制 二、代码 实现一 1. 代码实现 #include <stdio.h>int main(void){printf("------------------------------------\n\ Province Area(km2) Pop.(10K)\n\ ------------------…

14|CAMEL:通过角色扮演脑暴一个鲜花营销方案

能否让 ChatGPT 自己生成这些引导文本呢&#xff1f; CAMEL 交流式代理框架 CAMEL 框架旨在通过角色扮演来促进交流代理之间的自主合作&#xff0c;并为其“认知”过程提供洞察。这种方法涉及使用启示式提示来指导聊天代理完成任务&#xff0c;同时保持与人类意图的一致性。…

【virtio-networking 和 vhost-net 简介】

文章目录 Virtio 基本构建块Virtio spec 和 vhost 协议Vhost-net/virtio-net architectureVirtio-networking and OVS总结参考链接 Virtio 是作为虚拟机 (VM)访问简化device&#xff08;如块设备和网络适配器&#xff09;的 标准化开放接口而开发的。Virtio-net是一种虚拟以太…

大众EA111发动机

大众EA111发动机_什么是大众EA111发动机_太平洋汽车百科 大众EA111发动机_什么是大众EA111发动机_太平洋汽车百科 大众的EA111系列发动机是大众公司小排量发动机的主力&#xff0c;有1.2L、1.4L、1.6L三种排量。大众的EA111系列发动机融合了缸内直喷、涡轮增压等先进技术&…

鸿蒙Harmony应用开发—ArkTS-转场动画(页面间转场)

当路由进行切换时&#xff0c;可以通过在pageTransition函数中自定义页面入场和页面退场的转场动效。详细指导请参考页面转场动画。 说明&#xff1a; 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 为了实现更好的转场效…

稀碎从零算法笔记Day22-LeetCode:存在重复元素 II

题型&#xff1a;哈希表、数组 链接&#xff1a;219. 存在重复元素 II - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述 给你一个整数数组 nums 和一个整数 k &#xff0c;判断数组中是否存在两个 不同的索引 i 和 j &#xff0c;满足 nums[i] …

使用vitepress生成文档博客简单demo

先创建个空目录(就是你的项目) 安装vitepress 就是在你刚创建的目录里安装vitepress&#xff1a; npm add -D vitepress初始化项目 还是在你刚操作的目录里执行&#xff1a; npx vitepress init然后按照命令行的指引一步一步走就好了 注意VitePress的项目位置&#xff0c…

外卖项目:实现用户端微信登录(debug)

文章目录 一、业务描述二、接口设计三、表结构设计四、配置文件五、断点调试 一、业务描述 用户进入到小程序的时候&#xff0c;微信授权登录之后才能点餐。需要获取当前微信用户的相关信息&#xff0c;比如昵称、头像等&#xff0c;这样才能够进入到小程序进行下单操作。是基…

SpringBoot如何写好单元测试

&#x1f413;序言 Spring中的单元测试非常方便&#xff0c;可以很方便地对Spring Bean进行测试&#xff0c;包括Controller、Service和Repository等Spring Bean进行测试&#xff0c;确保它们的功能正常&#xff0c;并且不会因为应用的其他变化而出现问题。 &#x1f413;单元测…

完全理解ARM启动流程:Uboot-Kernel

内容共计5W字数&#xff0c;但是我还是很多地方说的不够尽兴。那么下次聊&#xff01; 前言 bootloader是系统上电后最初加载运行的代码。它提供了处理器上电复位后最开始需要执行的初始化代码。 PC机上引导程序一般由BIOS开始执行&#xff0c;然后读取硬盘中位于MBR(Main Bo…

Vue核心知识点 -Vue2响应式系统是基于什么实现的、以及会产生什么问题和解决方案

一、概念 在Vue 2中&#xff0c;响应式系统是基于Object.defineProperty实现的。它通过劫持对象的属性来实现数据的响应式更新。 当你将一个对象传递给Vue实例的data选项时&#xff0c;Vue会遍历对象的每个属性&#xff0c;并使用Object.defineProperty方法将其转换为getter和s…