优先级队列(2)_数据流中第k大元素
个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创优先级队列(2)_数据流中第k大元素
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌
目录
1. 题目链接
2. 题目描述
3. 解法
算法思路:
代码展示:
1. 题目链接
OJ链接 : 数据流中第k大元素
https://leetcode.cn/problems/kth-largest-element-in-a-stream/description/
2. 题目描述
设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。
请实现 KthLargest 类:
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后,返回当前数据流中第k大的元素。
示例 1:
输入:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出:[null, 4, 5, 5, 8, 8]
解释:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8
示例 2:
输入:
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
输出:[null, 7, 7, 7, 8]
解释:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // 返回 7
kthLargest.add(10); // 返回 7
kthLargest.add(9); // 返回 7
kthLargest.add(9); // 返回 8
提示:
0 <= nums.length <= 1041 <= k <= nums.length + 1-104 <= nums[i] <= 104-104 <= val <= 104- 最多调用
add方法104次
3. 解法
算法思路:
这道题是经典的top-k问题, 使用堆来解决:
1. 创建一个大小为k的堆 (大根堆 or 小根堆)
2, 循环:
a. 依次jindui
b. 判断堆的大小是否超过k
使用大根堆还是小根堆?
这里很明显需要使用小根堆, 因为我们需要取第k大的元素, 在小根堆中就是堆顶元素
代码展示:
class KthLargest {priority_queue<int, vector<int>, greater<int>> heap;int _k;
public:KthLargest(int k, vector<int>& nums) {_k = k;for(auto num : nums){heap.push(num);if(heap.size() > _k) heap.pop();} }int add(int val) {heap.push(val);if(heap.size() > _k) heap.pop();return heap.top(); }
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/
知识补充:
我们建的堆默认是大顶堆
greater<int>: 这是 C++ 标准库中的一个函数对象(或称为仿函数),它会对两个元素进行比较。如果第一个元素小于第二个元素,它返回 true;否则返回 false。换句话说,它表示一种“升序”的排序。

相关文章:
优先级队列(2)_数据流中第k大元素
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 优先级队列(2)_数据流中第k大元素 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌 目…...
【CSS】纯CSS Loading动画组件
<template><div class"ai-loader-box"><!-- AI loader --><div class"ai-loader"><div class"text"><p>AI智能分析中....</p></div><div class"horizontal"><div class&quo…...
rootless模式下istio ambient鉴权策略
环境说明 rootless模式下测试istio Ambient功能 四层鉴权策略 这里四层指的是网络通信模型的第四层,主要的传输协议为TCP和UDP。 用于限制服务间的通信,比如下面的策略应用于带有 app: productpage 标签的 Pod, 并且仅允许来自服务帐户 clus…...
超详细的总结!最新大模型算法岗面试题(含答案)来了!
大模型应该是目前当之无愧的最有影响力的AI技术,它正在革新各个行业,包括自然语言处理、机器翻译、内容创作和客户服务等,正成为未来商业环境的重要组成部分。 截至目前大模型已超过200个,在大模型纵横的时代,不仅大模…...
vmware-17pro全网最细安装教程(图文讲解,不需注册账户)
文章目录 一、下载安装包: 二、安装教程: 三、检查是否安装成功 四、许可证密匙 vmware安装教程 一、下载安装包: 链接:https://pan.baidu.com/s/1yC610SU1-O9Jtk7nUrZuSA?pwdsKBy 提取码:sKBy 二、安装教程&…...
C/C++(二)C++入门基础
这一章会介绍C入门必须掌握的一些基础概念。 一、函数重载 1、什么是函数重载? 函数重载是C相比于C语言的一个重大改进。 即C允许在同一作用域内声明多个功能类似的同名函数,这些函数的参数类型 / 个数 / 类型顺序不同。(注:返回…...
人工智能发展:一场从“被教导”到“自我成长”的奇妙冒险
说到人工智能(AI),大家的第一反应往往是机器人、无人驾驶、或者那个让人害怕的AI会不会取代人类。其实,AI的进化过程简直像一部精彩的电影,有起伏、有高潮、有让人摸不着头脑的时刻。今天,我们就一起来“吃…...
企业级 RAG 全链路优化关键技术
本文根据2024云栖大会实录整理而成,演讲信息如下: 演讲人: 邢少敏 | 阿里云智能集团高级技术专家 活动: 2024 云栖大会 - AI 搜索企业级 RAG 全链路优化关键技术 在2024云栖大会上,阿里云 AI 搜索研发负责人之一的…...
学习文档(5)
Redis应用 目录 Redis应用 Redis 除了做缓存,还能做什么? Redis 可以做消息队列么? Redis 可以做搜索引擎么? 如何基于 Redis 实现延时任务? Redis 除了做缓存,还能做什么? 分布式锁&…...
node.js下载安装以及环境配置超详细教程【Windows版本】
node安装以及环境变量配置 Step1:选择版本进行安装Step2:安装Node.jsStep3:环境配置Step4:检查node.js是否成功安装Step5:npm修改下载镜像 Step1:选择版本进行安装 Node.js 安装包及源码下载地址为 Node.…...
08_实现 reactive
目录 编写 reactive 的函数签名处理对象的其他行为拦截 in 操作符拦截 for...in 循环delete 操作符 处理边界新旧值发生变化时才触发依赖的情况处理从原型上继承属性的情况处理一个对象已经是代理对象的情况处理一个原始对象已经被代理过一次之后的情况 浅响应与深响应代理数组…...
finereport 中台 帆软 编码解码
帆软用的 post 方式编码不是用的 dict,而是二次 url 编码,需要二次解析 import time import urllib.parse import json# 原始字符串 encoded_string data "__parameters__%7B%22MANUFACTURER%22%3A%22%22%2C%22CATEGORY%22%3A%22%22%2C%22HHPN_L…...
Day15-数据库服务全面优化与PT工具应用
Day15-数据库服务全面优化与PT工具应用 1、数据库服务优化讲解1.2 数据库服务系统层面的优化1.3 数据库服务软件版本选择1.4 数据库服务结构参数优化1.4.1 数据库连接层优化1.4.2 数据库服务层优化1.4.3 数据库引擎层优化1.4.4 数据库复制相关优化1.4.5 数据库其他相关优化 1.5…...
开源限流组件分析(二):uber-go/ratelimit
文章目录 本系列漏桶限流算法uber的漏桶算法使用mutex版本数据结构获取令牌松弛量 atomic版本数据结构获取令牌测试漏桶的松弛量 总结 本系列 开源限流组件分析(一):juju/ratelimit开源限流组件分析(二):u…...
探索 SVG 创作新维度:svgwrite 库揭秘
文章目录 **探索 SVG 创作新维度:svgwrite 库揭秘**背景介绍库简介安装指南基础函数使用实战场景常见问题与解决方案总结 探索 SVG 创作新维度:svgwrite 库揭秘 背景介绍 在数字艺术和网页设计领域,SVG(Scalable Vector Graphic…...
为什么要做PFAS测试?PFAS检测项目详细介绍
PFAS测试之所以重要,主要归因于PFAS(全氟和多氟化合物)的广泛存在、持久性、生物累积性和潜在的毒性。这些特性使得PFAS在环境和人体中可能长期存在,并对生态系统和人类健康构成威胁。以下是对PFAS检测项目的详细介绍以及进行PFAS…...
稀土阻燃协效剂的应用
稀土阻燃协效剂是一类利用稀土元素(如铈、镧、钕、铕等)具有的独特性质,来增强材料阻燃性能的化学物质。在聚合物材料燃烧时可催化酯花成碳,迅速在高分子表面形成致密连续的碳层,隔绝聚合物材料内部的可燃性气体与氮气…...
Java的异常处理
常见异常 ① 运行时异常 a、ClassNotFoundException b、FileNotFoundException c、IOException ② 编译时异常 a、ArrayIndexOutOfBoundsException b、NullPointerException c、ClassCastException d、InputFormatException e、InputMismatchException f、ArithmeticException …...
免费域名邮箱申请和使用教程:有哪些步骤?
免费域名邮箱设置指南?如何免费注册烽火域名邮箱? 对于个人和企业而言,拥有一个专属的域名邮箱不仅能提升专业形象,还能增强品牌识别度。烽火将详细介绍如何申请和使用免费域名邮箱,帮助您轻松拥有一个专属的电子邮件…...
Linux之实战命令45:swapon应用实例(七十九)
简介: CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布:《Android系统多媒体进阶实战》🚀 优质专栏: Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏: 多媒体系统工程师系列【…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
