February——703. 数据流中的第 K 大元素&堆的总结以及API的使用_kth/api-程序员宅基地

技术标签: 算法  python  java    数组  leetcode  Leetcode  数据结构  

聊今天这个题目之前先聊聊一个数据结构:堆。堆又分为最大堆和最小堆。 父节点的值总是大于或者等于任何一个子节点的值时为最大堆。父节点的值总是小于或者等用户任何一个子节点的值时为最小堆。其实说白了就是一个完全二叉树的数据结构。如下图所示,左边是最大堆,右边是最小堆

最大堆和最小堆的应用和优先队列差不多,每次都能弹出一个最大值或者最小值,当然在python中也有相应API。接下来堆API的方法大致说明一下:

#导入堆
import heapq

#将list转化堆
heapq.heapify(x)
#将item添加到堆中,保持堆的不变性
heapq.heappush(heap, item)
#弹出并返回heap中的最小元素
heapq.heappop(heap)
#将 item 放入堆中,然后弹出并返回 heap 的最小元素。该组合操作比先调用  heappush() 再调用 heappop() 运行起来更有效率。
heapq.heappushpop(heap, item)
#弹出并返回 heap 中最小的一项,同时推入新的 item。 堆的大小不变
heapq.heapreplace(heap, item)

#返回前n个最大或者最小的元素
heapq.nlargest(n, iterable, key=None)
heapq.nsmallest(n, iterable, key=None)
#将多个已排序的输入合并为一个已排序的输出
heapq.merge(*iterables, key=None, reverse=False)

 分析:该题目求第K大元素,那我门可以构造一个最小堆,这个堆的大小保持为k个元素,堆顶的元素恰好就是第K大元素。

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
       
        #维护一个最小堆,堆顶的元素是最小的
        self.k = k
        self.heap = nums   
        heapq.heapify(self.heap)
        #堆顶的元素不断弹出,维护一个含有K个元素大小的最小堆
        while len(self.heap) > k:
            heapq.heappop(self.heap)


    def add(self, val: int) -> int:
        #将元素添加到最小堆中去
        heapq.heappush(self.heap,val)
        #添加之后的元素如果大于k,那就弹出堆顶元素
        if len(self.heap)>self.k:
            heapq.heappop(self.heap)

        #返回堆顶元素
        return self.heap[0]



# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

总结:Python的API中只实现了最小堆,并没有实现最大堆。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_37724529/article/details/113842674

智能推荐

C编程 汇集(转自YJ)_c1rspjuigpx7bccv%%%-程序员宅基地

文章浏览阅读874次。◆经典C源程序100例:http://post.baidu.com/f?kz=8618367 ◆时钟的驻留程序:http://post.baidu.com/f?kz=10822377 ◆数据结构暨若干经典问题和算法:http://post.baidu.com/f?kz=10922856 ◆LIUXUY 磁盘系统源程序:http://post.baidu.com/f?kz=1297334_c1rspjuigpx7bccv%%%

安卓按键响应四种方式_android 休眠,按键响应-程序员宅基地

文章浏览阅读2.2k次,点赞2次,收藏11次。目录标题一、按键响应方式一1.1 绑定onclick函数1.2 按键响应函数实现1.3 效果二、按键响应方式二2.1 定义监听器接口2.2 绑定响应接口2.3 效果三、按键响应方式三3.1 定义变量Button3.2 绑定局部变量Button和xml中button3.3 设置按键响应3.4 效果四、按键响应方式四一、按键响应方式一1.1 绑定onclick函数当按键被按下就会去执行函数buttonBeClicked1.2 按键响应函数实现在MainActivity.java文件中去添加响应函数_android 休眠,按键响应

前端meta标签_前端开发meta标签-程序员宅基地

文章浏览阅读52次。meta主要用于设置网页的一些元数据,元数据不是给用户看的。 charset用于指定网页的字符集,<meta charset = "utf-8"> name 元数据的名称,content元数据的数据值;name常用的有:keywrods 关键字 <meta name="Keywords" content="网上购物,网上商城,家电,手机,电脑,服装,居家,母婴,美妆,个护,食品,生鲜,京东"/> decription 描述 : <m_前端开发meta标签

在SpringBoot中使用MockMvc和Junit进行单元测试_springboot junit-jupiter mockmvc-程序员宅基地

文章浏览阅读2.5k次。Mock在面向对象的程序设计中,模拟对象(英语:mock object)是以可控的方式模拟真实对象行为的假对象。在编程过程中,通常通过模拟一些输入数据,来验证程序是否达到预期结果。使用Mockito一般分三个步骤:1、模拟测试类所需的外部依赖;2、执行测试代码;3、判断执行结果是否达到预期。MockMvc基于RESTful风格的SpringMVC单元测试,可以测试完整的SpringMVC流程,即从URL请求到控制处理器,带到视图渲染都可以测试。MockMvc是由spring-test包提供,实_springboot junit-jupiter mockmvc

RK3288[android 7.1]调试笔记 移除u-boot层logo显示,保留kernel层logo显示_rk3288 内核logo不显示-程序员宅基地

文章浏览阅读3.4k次,点赞2次,收藏12次。1 把uboot层logo的显示关闭修改\u-boot\drivers\video\rockchip_display.c文件dongsy@build-server-100:~/work/dsy/rk3288-Android-7.0/u-boot(edp-lvds)$ git diff drivers/video/rockchip_display.cdiff --git a/drivers/v..._rk3288 内核logo不显示

异步fifo设计及验证verilog代码_异步fifo验证-程序员宅基地

文章浏览阅读337次。异步fifo设计及验证verilog代码_异步fifo验证

随便推点

vue 自定义注册全局notification消息通知组件_在vue中如何弄一个notification 全局通知-程序员宅基地

文章浏览阅读9.7w次。效果图目录结构Notice.vue<template> <transition name="notice-fade"> <div v-if="visible" :class="wrapClasses"> <span class="content"> <i v-if="type === 'succe..._在vue中如何弄一个notification 全局通知

nginx: [error] invalid PID number "" in "/usr/local/webserver/nginx/logs/nginx.pid"-程序员宅基地

文章浏览阅读1.2k次。nginx -c /usr/local/webserver/nginx/conf/nginx.confnginx -s reload安装nginx1. tar xvzf ./configure --prefix=/usr/local/nginxyum -y install pcre*yum -y install zlib-devel2.

基于ARM9 编写LED汇编程序_arm9.芯片程序-程序员宅基地

文章浏览阅读1k次。下定决心考研了,把之前的写的笔记都整理整理^-^!ARM芯片启动过程(大多数芯片从0地址启动)1)NOR启动: 1.NOR Flash的基地址为0,片内RAM为0x4000 0000;2.CPU读出NOR上的第一个指令(前4字节),执行CPU继续读出其他指令执行。2)Nand启动:1.片内4K RAM基地址为0,NoR Flash 不可访问; 注:stepping stone是三星MCU的一种启动..._arm9.芯片程序

2021-01-24-程序员宅基地

文章浏览阅读212次。学什么东西都好,可能对于别人来说确实是迟了,但是对于自己来说,永远都不会算迟,增值自己应该是一辈子都在做的事情。我恰好也是大三,专业软件工程,主要做移动开发,现在是在做Android开发。我学校普通2A,环境不怎么样,师资不怎样。对我来说,基本所有编程得知识都是来自于书本和网络。既然现在开始还没有迟,那么就让我分享下我的想法,题主参考下,按重要程度降序排列。**① 强迫自己解决问题。**很多时候,我们的思维都是,学习、不懂、太难了、不想学、放弃。但是实际上问题都没有想象中的难,如果我们一开始就怕太难

最新Vue2.0+组件开源项目库集合_vue2.0项目推荐-程序员宅基地

文章浏览阅读573次。UI组件element ★11612 - 饿了么出品的Vue2的web UI工具套件Vux ★7503 - 基于Vue和WeUI的组件库iview ★5801 - 基于 Vuejs 的开源 UI 组件库mint-ui ★5517 - Vue 2的移动UI元素vue-material ★2790 - 通过Vue Material和Vue 2建立精美的app应用muse-ui ★2..._vue2.0项目推荐

【解决错误】ImportError: No module named seaborn_no module named seaborn命令行怎么解决-程序员宅基地

文章浏览阅读7k次,点赞2次,收藏3次。1. pip安装:pip install seaborn2. conda安装:conda install seaborn_no module named seaborn命令行怎么解决