热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

LeetCodeMergeKsortedLists

Merge k sortedlinkedlistsandreturnitasonesortedlist.Analyzeanddescribeitscomplexity.

Merge k sorted
linked lists and return it as one sorted list. Analyze and describe its complexity.

采用最小堆,首先将 k 个首节点放入堆中,弹出最小的节点并插入到新的链表中;

                     弹出的节点如果next 非空,就将它的 下一个节点进 堆。 

                     继续,直到堆为空。

堆 Push 和 pop 的复杂度是 log(k), 所以复杂度是 nlg(k), n为总的节点数;


/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
int K = lists.size();
if (K == 0) return NULL;
else if (K == 1) return lists[0];

ListNode *listHead(NULL), *listRear(NULL);
ListNode *node(NULL);
priority_queue, cmp> h;

// push K list heads into heap
for(int i=0; i if(lists[i] != NULL){
h.push(lists[i]);
lists[i] = lists[i]->next;
}

while(!h.empty()){
//pop the min of k nodes
node = h.top(); h.pop();
if(node->next)
h.push(node->next);

//insert node into new list
if(listRear){
listRear->next = node;
listRear = listRear->next;
}
else{
listHead = listRear = node;
}
}

return listHead;
}
private:
struct cmp{
bool operator()(ListNode* lhs, ListNode *rhs){
if(lhs->val val) return false;
else return true;
}
};
};


推荐阅读
  • 基于layUI的图片上传前预览功能的2种实现方式
    本文介绍了基于layUI的图片上传前预览功能的两种实现方式:一种是使用blob+FileReader,另一种是使用layUI自带的参数。通过选择文件后点击文件名,在页面中间弹窗内预览图片。其中,layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块,并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]
  • 本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用,包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]
  • Redis底层数据结构之压缩列表的介绍及实现原理
    本文介绍了Redis底层数据结构之压缩列表的概念、实现原理以及使用场景。压缩列表是Redis为了节约内存而开发的一种顺序数据结构,由特殊编码的连续内存块组成。文章详细解释了压缩列表的构成和各个属性的含义,以及如何通过指针来计算表尾节点的地址。压缩列表适用于列表键和哈希键中只包含少量小整数值和短字符串的情况。通过使用压缩列表,可以有效减少内存占用,提升Redis的性能。 ... [详细]
  • 在编写业务代码时,常常会遇到复杂的业务逻辑导致代码冗长混乱的情况。为了解决这个问题,可以利用中间件模式来简化代码逻辑。中间件模式可以帮助我们更好地设计架构和代码,提高代码质量。本文介绍了中间件模式的基本概念和用法。 ... [详细]
  • 本文介绍了一道网络流题目hdu4888 Redraw Beautiful Drawings的解题思路。题目要求以行和列作为结点建图,并通过最大流算法判断是否有解以及是否唯一。文章详细介绍了建图和算法的过程,并强调在dfs过程中要进行回溯。 ... [详细]
  • 本文介绍了使用Python解析C语言结构体的方法,包括定义基本类型和结构体类型的字典,并提供了一个示例代码,展示了如何解析C语言结构体。 ... [详细]
  • 实现一个通讯录系统,可添加、删除、修改、查找、显示、清空、排序通讯录信息
    本文介绍了如何实现一个通讯录系统,该系统可以实现添加、删除、修改、查找、显示、清空、排序通讯录信息的功能。通过定义结构体LINK和PEOPLE来存储通讯录信息,使用相关函数来实现各项功能。详细介绍了每个功能的实现方法。 ... [详细]
  • 本文介绍了一种图的存储和遍历方法——链式前向星法,该方法在存储带边权的图时时间效率比vector略高且节省空间。然而,链式前向星法存图的最大问题是对一个点的出边进行排序去重不容易,但在平行边无所谓的情况下选择这个方法是非常明智的。文章还提及了图中搜索树的父子关系一般不是很重要,同时给出了相应的代码示例。 ... [详细]
  • 本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值,函数可以作为变量自由传递,也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性,为程序开发带来了便利。 ... [详细]
  • 本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址,通过指针可以修改指针所指的变量的值。然而,如果想要修改指针的指向,就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法,并思考了在修改指针的指向后,取指针的输出结果。 ... [详细]
  • 在project.properties添加#Projecttarget.targetandroid-19android.library.reference.1..Sliding ... [详细]
  • 猜字母游戏
    猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]
  • CentOS 7部署KVM虚拟化环境之一架构介绍
    本文介绍了CentOS 7部署KVM虚拟化环境的架构,详细解释了虚拟化技术的概念和原理,包括全虚拟化和半虚拟化。同时介绍了虚拟机的概念和虚拟化软件的作用。 ... [详细]
  • 本文介绍了一种解析GRE报文长度的方法,通过分析GRE报文头中的标志位来计算报文长度。具体实现步骤包括获取GRE报文头指针、提取标志位、计算报文长度等。该方法可以帮助用户准确地获取GRE报文的长度信息。 ... [详细]
  • PDF内容编辑的两种小方法,你知道怎么操作吗?
    本文介绍了两种PDF内容编辑的方法:迅捷PDF编辑器和Adobe Acrobat DC。使用迅捷PDF编辑器,用户可以通过选择需要更改的文字内容并设置字体形式、大小和颜色来编辑PDF文件。而使用Adobe Acrobat DC,则可以通过在软件中点击编辑来编辑PDF文件。PDF文件的编辑可以帮助办公人员进行文件内容的修改和定制。 ... [详细]
author-avatar
手机用户2502938311
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有