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

智能推荐

【九度】题目1090:路径打印 && 【LeetCode】Simplify Path_打印目录结构 leetcode-程序员宅基地

文章浏览阅读1.3k次。1、题目1090:路径打印时间限制:1 秒内存限制:32 兆特殊判题:否提交:1319解决:230题目描述:给你一串路径,譬如:a\b\ca\d\eb\cstd\你把这些路径中蕴含的目录结构给画出来,子目录直接列在父目录下面,并比父目录向右缩一格,就像这样:a b c d eb cstd同一级的需要按字母顺序_打印目录结构 leetcode

如何使用Cordova将SAP Fiori应用打包并安装到Android平台上_fiori发布安卓-程序员宅基地

文章浏览阅读591次。There is a wonderful tutorial Building SAP Fiori-like UIs with SAPUI5 in 10 Exercises written by Bertram Ganz.In this blog, I will show step by step how to package the UI5 application built by this tutorial as a native application into your Android device_fiori发布安卓

程序员代码面试指南下(7-9)-程序员宅基地

文章浏览阅读182次。目录第7章 1 不用额外变量交换两个整数的值(士 ★☆☆☆) 2 不用任何比较判断找出两个数中较大的数(校★★★☆) 3 只用位运算不用算术运算实现整数的加减乘除运算 4 整数的二进制表达中有多少个1 5 在其他数都出现偶数次的数组中找到出现奇数次的数 6 在其他数都出现A次的数组中找到只出现一次的数第8章 1 转圈打印矩阵 2 将正方形矩阵顺时针转动90度 3 之..._if (map.containskey(xor)) { int pre = map.get(xor); mosts[i] = pre =

uva-1399 Puzzle-程序员宅基地

文章浏览阅读152次。AC自动机上的dp

C++中 sprintf函数的用法_sprintf %c-程序员宅基地

文章浏览阅读871次。C++中 sprintf函数的用法1.常用方式sprintf函数的功能与printf函数的功能基本一样,只是它把结果输出到指定的字符串中了,看个例子就明白了:例:将”test 1 2”写入数组s中#include<stdio.h>int main(int argc, char *avgv[]){ char s[40]; sprintf(s,"%s%d..._sprintf %c

Java开发的医院门诊挂号系统_医院预约挂号er图-程序员宅基地

文章浏览阅读2.2k次。医院门诊系统,挂号预约系统,有四个角色(管理员,医生,护士,普通用户)_医院预约挂号er图

随便推点

Android Socket Demo [ 附客户端与服务端源码 ]_android socket客户端下载-程序员宅基地

文章浏览阅读818次。如果要跑通demo首先: 服务端我是用 intellij idea 开发的。如果用其他软件打跑不起来就用 intellij其次: 要将手机跟电脑连在同个网络下最后: Constants的ip地址要填写上电脑的ip地址实现功能:客户端连接服务端,客户端发数据到服务端,客户端收到服务端发来的数据服务端收到客户端发的数据,服务端发数据给客户端贴部分核心代码客户端连接服务端:首先客户端连接服务端必须要在线程里(后面的是 ip地址 跟端口,端口是服务端的socke..._android socket客户端下载

定制win10桌面_win10联想 自带主题-程序员宅基地

文章浏览阅读1.3k次,点赞4次,收藏7次。壁纸在文末先上几张美化后的照片 主题链接win 10 美化相信很多人都厌倦了win10原装主题了,陈旧的窗口边框,一如既往的图标,老掉牙的窗口样式和菜单栏……算了,就不吐槽了,直接上教程吧!前方高能第零步关掉杀毒软件(新手建议卸载),这点非常重要,如某数字,某讯,某霸,如果关掉以后放心不下自己电脑的安全,以下文章请勿食用!(后果自负)第一步破解原装win10系统主题。友..._win10联想 自带主题

jQuery懒加载插件 – jquery.lazyload.js简单调用-程序员宅基地

文章浏览阅读57次。 Lazy Load 是一个用 JavaScript 编写的 jQuery 插件. 它可以延迟加载长页面中的图片. 在浏览器可视区域外的图片不会被载入, 直到用户将页面滚动到它们所在的位置. 这与图片预加载的处理方式正好是相反的.在包含很多大图片长页面中延迟加载图片可以加快页面加载速度. 浏览器将会在加载可见图片之后即进入就绪状态. 在某些情况下还可以帮助降低服务器负担。一、下载和引用  ..._jq.lazyload.js配置

mysql_172.25.2.1-程序员宅基地

文章浏览阅读404次。一.cmake升级https://cmake.org/download/ #cmake下载地址 yum install jsoncpp-0.10.5-2.el7.x86_64.rpm jsoncpp-devel-0.10.5-2.el7.x86_64.rpm -y yum install cmake3-3.6.1-2.el7.x86_64.rpm cmake3-data-3.6.1-2.el7.noarch.rpm -y二.mysql编译安装升级gcctar zxf mysql-boost-_172.25.2.1

基于Numpy的线性代数运算_numpy线性代数运算-程序员宅基地

文章浏览阅读737次。标题中的英文首字母大写比较规范,但在python实际使用中均为小写。1.Numpy中的matrix1.1 创建matrix对象numpy.matrix方法的参数可以为ndarray对象numpy.matrix方法的参数也可以为字符串str,示例如下:import numpy as npm = np.matrix("1 2 3;4 5 6; 7 ..._numpy线性代数运算

搭建LAMP环境(源码方式)_this software is subject to the php license, avail-程序员宅基地

文章浏览阅读3.7k次。源码方式,搭建LAMP环境。_this software is subject to the php license, available in this | | distribut

推荐文章

热门文章

相关标签