首页 > 编程语言 >合并k个有序列表-python

合并k个有序列表-python

时间:2022-08-31 20:46:29浏览次数:72  
标签:index heapq 序列表 python 合并 queues list 队列 heap

主要思路:借鉴堆、队列特点,构建新的有序结果

# merge the k sorted list
# main idea: 将每个list放入队列,初始一个小顶堆,size为list个数,value为队列的首个元素,交替寻找最小值存储到新list中
import heapq
from collections import deque
nums = [[1,3,43], [16,29,89], [4, 33, 88, 100,1011]]
# 队列化
queues = list(map(deque, nums))
heap = []
for i, q in enumerate(queues):
    heap.append((q.popleft(), i))
# 堆化,弹出最小值:
heapq.heapify(heap)
result = []
while heap:
    # 弹出最小元素
    val, index = heapq.heappop(heap)
    result.append(val)
    # 找出弹出元素所在队列中的下一个元素,push到堆中,重复以上步骤
    if queues[index]:
        new_num = queues[index].popleft()
        heapq.heappush(heap, (new_num, index))
result

 

参考:https://izsk.me/2019/03/02/%E5%90%88%E5%B9%B6K%E4%B8%AA%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84(python)/

标签:index,heapq,序列表,python,合并,queues,list,队列,heap
From: https://www.cnblogs.com/demo-deng/p/16644450.html

相关文章

  • python进阶__struct数据处理详解
    一、此模块可以执行Python值和以Pythonbytes对象表示的C结构之间的转换二、打包解包需要按照特定的方式来打包或者解包.该方式就是格式化字符串,它指定了数据类......
  • python怎么将json转成字符串
    在python中将json转成字符串的方法:首先打印出数据的类型;然后输入“str=json.dumps(data,indent=2)”命令将json转换为字符串,最后使用print语句打印出字符串即可。pyth......
  • Python入门系列(六)一篇学会python函数
    函数函数是只在调用时运行的代码块。defmy_function():print("Hellofromafunction")my_function()信息可以作为参数传递到函数中。defmy_function(fname):......
  • 这个Python读取文件的方法,堪称天花板级别...
    序言哈喽兄弟们,今天咱们来了解一下fileinput。说到fileinput,可能90%的码农表示没用过,甚至没有听说过。这不奇怪,因为在python界,既然open可以走天下,何必要filein......
  • Python自学笔记11-函数的定义和调用
    函数是组织代码的非常有效的方式,有了函数,我们就可以编写大规模的项目。可以说,函数是组织代码的最小单元。Python函数的定义函数是代码封装的一种手段,函数中包含一段可以......
  • Python爬虫-BeautifulSoup基本用法(三)
    BeautifulSoup基本用法BeautifulSoup是Python的一个HTML或XML的解析库,可以用它来方便地从网页提取数据(以下为崔庆才的爬虫书的学习笔记)一.安装方式#安装beautifulsoup......
  • python 修改列表元素
    修改列表的元素时,可以使用for循环结合range n=int(input())list_b=[[1,2,3],[4,5,6],[7,8,9]]foriinrange(len(list_b)):  foryinrange(len(l......
  • jenkins-配置python
    1.进入"Dashboard"界面,点击左侧"构建执行状态"2.点击列表设置图标3.勾选"Environmentvariables",点击"新增",输入环境变量【名称和python路径】,点击保存4.查看......
  • python-去除txt文件空格、特殊字符
    #!/usr/bin/python#-*-coding:UTF-8-*-"""@author:Roc-xb"""importre#导入re#去除图片文字内空格、特殊字符withopen("E:\\test001\\001test.txt","r"......
  • python 根据dic的value去区key的值,直接用函数
    defget_keys(d,value):return[kfork,vind.items()ifv==value]get_keys({'a':'001','b':'002'},'001')#=>['a'] 字符串里面有参数用ftinydic......