软件测试工程师 ssis datepicker 管理后台模板 android项目开发 pip环境变量配置 jq入口函数 winbox使用教程 bootstrap颜色 pyhton中异常和模块 郑州普通话 python中index的用法 python例子 python变量定义 python模块下载 java学习课程 java获取文件大小 java正则匹配数字 java中string的方法 java判断 java系统学习 python教程视频 mac地址修改器 网站数据分析工具 删除数组中的某个元素 图片链接生成器 动态加载js 华为线刷工具 js延迟加载的方式 选择模拟位置信息应用 fireworks8序列号 robotstudio 8元秒电脑 assist是什么意思 js保留两位小数 comsol下载 奥法隐藏外观 jsp源代码 马颂德 全能音频转换通
当前位置: 首页 > 学习教程  > 编程语言

力扣刷题Python笔记:合并K个升序链表

2020/10/8 19:43:46 文章标签:

题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 来源:力扣(LeetCode) python解法 这道题用到了一种以前刷题没遇到过的数据结构——堆(h…

题目

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。
在这里插入图片描述

来源:力扣(LeetCode)

python解法

这道题用到了一种以前刷题没遇到过的数据结构——堆(heap),它是一种优先队列,能够让你以任意顺序添加对象,并且随时可以找出最小队列。它的效率高于列表中的min函数。

实际上,Python中并没有独立的堆类型,只有一个包含一些堆操作函数的模块——heapq(字母q表示队列)。heapq模块中有6个函数如下表所示,我们必须用列表来表示堆对象本身。

函数说明
heappush(heap, i)把元素 i 压入堆heap中
heappop(heap)从堆heap中取出最小元素
heapify(heap)让列表heap具备堆的特征
heapreplace(heap, x)从堆heap中取出最小元素,并把元素x压入堆heap中
nlargest(n, heap)找出堆heap中前n个最大的元素
nsmallest(n, heap)找出堆heap中前n个最小的元素

具体解题思路如下:
①创建堆(列表)minheap,用来存放每个链表当前遍历到的节点;
②从每个链表中找到不为空的头结点,将该结点的值以及对应的索引(Lists中的第几个链表)放入堆minheap中;
③创建一个用来存放结果链表的头结点start以及移动结点cur_node;
④从minheap中取出最小值以及对应的索引 index,将cur_node.next指向该结点(注意是指向结点而不是指向值);
⑤移动cur_node结点并更新索引index对应的链表头结点,如果新的头结点不为空,将其压入堆minheap中;
⑥当minheap不为空时,重复步骤④~⑤。

代码如下:

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    import heapq
    minheap = [] 
    # minheap用来存放每个链表当前遍历到的节点
    for index, node in enumerate(lists): # index代表这是第几个链表, node代表每个链表的头结点
        if node != None:  
        # 如果头结点不空,把它放入堆minheap中
            heapq.heappush(minheap, (node.val, index)) 
            # 将当前头结点的value以及所在的链表index入堆

    start = ListNode() # 用来存放结果
    cur_node = start      
    while minheap:  
        val, index = heapq.heappop(minheap) 
        # 堆内value最小的出堆,同时找到链表索引index,方便寻找下一个位置
        cur_node.next = lists[index]       # 加入到结果链表中
        cur_node = cur_node.next                # 移动到结果链表的下一个位置
        lists[index] = lists[index].next # 找到当前链表的下一个元素
        if lists[index] != None:      # 如果不为空的话就入堆
            heapq.heappush(minheap, (lists[index].val, index)) # 下一个元素入堆
    return start.next

本文链接: http://www.dtmao.cc/news_show_250165.shtml

附件下载

上一篇:硬件SPI控制ST7789V

下一篇:10.2-10.8周记

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?