当前位置: 首页 > news >正文

优先级队列(2)_数据流中第k大元素

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

优先级队列(2)_数据流中第k大元素

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌
  

目录

1. 题目链接

2. 题目描述

3. 解法

算法思路:

代码展示: 


1. 题目链接

OJ链接 :  数据流中第k大元素icon-default.png?t=O83Ahttps://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 <= 104
  • 1 <= 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大元素

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 优先级队列(2)_数据流中第k大元素 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目…...

【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功能 四层鉴权策略 这里四层指的是网络通信模型的第四层&#xff0c;主要的传输协议为TCP和UDP。 用于限制服务间的通信&#xff0c;比如下面的策略应用于带有 app: productpage 标签的 Pod&#xff0c; 并且仅允许来自服务帐户 clus…...

超详细的总结!最新大模型算法岗面试题(含答案)来了!

大模型应该是目前当之无愧的最有影响力的AI技术&#xff0c;它正在革新各个行业&#xff0c;包括自然语言处理、机器翻译、内容创作和客户服务等&#xff0c;正成为未来商业环境的重要组成部分。 截至目前大模型已超过200个&#xff0c;在大模型纵横的时代&#xff0c;不仅大模…...

vmware-17pro全网最细安装教程(图文讲解,不需注册账户)

文章目录 一、下载安装包&#xff1a; 二、安装教程&#xff1a; 三、检查是否安装成功 四、许可证密匙 vmware安装教程 一、下载安装包&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1yC610SU1-O9Jtk7nUrZuSA?pwdsKBy 提取码&#xff1a;sKBy 二、安装教程&…...

C/C++(二)C++入门基础

这一章会介绍C入门必须掌握的一些基础概念。 一、函数重载 1、什么是函数重载&#xff1f; 函数重载是C相比于C语言的一个重大改进。 即C允许在同一作用域内声明多个功能类似的同名函数&#xff0c;这些函数的参数类型 / 个数 / 类型顺序不同。&#xff08;注&#xff1a;返回…...

人工智能发展:一场从“被教导”到“自我成长”的奇妙冒险

说到人工智能&#xff08;AI&#xff09;&#xff0c;大家的第一反应往往是机器人、无人驾驶、或者那个让人害怕的AI会不会取代人类。其实&#xff0c;AI的进化过程简直像一部精彩的电影&#xff0c;有起伏、有高潮、有让人摸不着头脑的时刻。今天&#xff0c;我们就一起来“吃…...

企业级 RAG 全链路优化关键技术

本文根据2024云栖大会实录整理而成&#xff0c;演讲信息如下&#xff1a; 演讲人&#xff1a; 邢少敏 | 阿里云智能集团高级技术专家 活动&#xff1a; 2024 云栖大会 - AI 搜索企业级 RAG 全链路优化关键技术 在2024云栖大会上&#xff0c;阿里云 AI 搜索研发负责人之一的…...

学习文档(5)

Redis应用 目录 Redis应用 Redis 除了做缓存&#xff0c;还能做什么&#xff1f; Redis 可以做消息队列么&#xff1f; Redis 可以做搜索引擎么&#xff1f; 如何基于 Redis 实现延时任务&#xff1f; Redis 除了做缓存&#xff0c;还能做什么&#xff1f; 分布式锁&…...

node.js下载安装以及环境配置超详细教程【Windows版本】

node安装以及环境变量配置 Step1&#xff1a;选择版本进行安装Step2&#xff1a;安装Node.jsStep3&#xff1a;环境配置Step4&#xff1a;检查node.js是否成功安装Step5&#xff1a;npm修改下载镜像 Step1&#xff1a;选择版本进行安装 Node.js 安装包及源码下载地址为 Node.…...

08_实现 reactive

目录 编写 reactive 的函数签名处理对象的其他行为拦截 in 操作符拦截 for...in 循环delete 操作符 处理边界新旧值发生变化时才触发依赖的情况处理从原型上继承属性的情况处理一个对象已经是代理对象的情况处理一个原始对象已经被代理过一次之后的情况 浅响应与深响应代理数组…...

finereport 中台 帆软 编码解码

帆软用的 post 方式编码不是用的 dict&#xff0c;而是二次 url 编码&#xff0c;需要二次解析 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版本数据结构获取令牌测试漏桶的松弛量 总结 本系列 开源限流组件分析&#xff08;一&#xff09;&#xff1a;juju/ratelimit开源限流组件分析&#xff08;二&#xff09;&#xff1a;u…...

探索 SVG 创作新维度:svgwrite 库揭秘

文章目录 **探索 SVG 创作新维度&#xff1a;svgwrite 库揭秘**背景介绍库简介安装指南基础函数使用实战场景常见问题与解决方案总结 探索 SVG 创作新维度&#xff1a;svgwrite 库揭秘 背景介绍 在数字艺术和网页设计领域&#xff0c;SVG&#xff08;Scalable Vector Graphic…...

为什么要做PFAS测试?PFAS检测项目详细介绍

PFAS测试之所以重要&#xff0c;主要归因于PFAS&#xff08;全氟和多氟化合物&#xff09;的广泛存在、持久性、生物累积性和潜在的毒性。这些特性使得PFAS在环境和人体中可能长期存在&#xff0c;并对生态系统和人类健康构成威胁。以下是对PFAS检测项目的详细介绍以及进行PFAS…...

稀土阻燃协效剂的应用

稀土阻燃协效剂是一类利用稀土元素&#xff08;如铈、镧、钕、铕等&#xff09;具有的独特性质&#xff0c;来增强材料阻燃性能的化学物质。在聚合物材料燃烧时可催化酯花成碳&#xff0c;迅速在高分子表面形成致密连续的碳层&#xff0c;隔绝聚合物材料内部的可燃性气体与氮气…...

Java的异常处理

常见异常 ① 运行时异常 a、ClassNotFoundException b、FileNotFoundException c、IOException ② 编译时异常 a、ArrayIndexOutOfBoundsException b、NullPointerException c、ClassCastException d、InputFormatException e、InputMismatchException f、ArithmeticException …...

免费域名邮箱申请和使用教程:有哪些步骤?

免费域名邮箱设置指南&#xff1f;如何免费注册烽火域名邮箱&#xff1f; 对于个人和企业而言&#xff0c;拥有一个专属的域名邮箱不仅能提升专业形象&#xff0c;还能增强品牌识别度。烽火将详细介绍如何申请和使用免费域名邮箱&#xff0c;帮助您轻松拥有一个专属的电子邮件…...

Linux之实战命令45:swapon应用实例(七十九)

简介&#xff1a; CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布&#xff1a;《Android系统多媒体进阶实战》&#x1f680; 优质专栏&#xff1a; Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a; 多媒体系统工程师系列【…...

补个基础:闭包和this指针调用

//定义了一个普通的函数 const search()>{console.log(search) } //定义了一个防抖函数 function debounce(fn,delay){let timer nullreturn (...args)>{clearTimeout(timer)timersetTimeout(()>{//为什么要apply&#xff0c;改变指针指向fn.apply(this,args)console.…...

Java继承详解:从基础到实战,吃透面向对象核心特性

哈喽&#xff0c;各位Java学习者&#xff01;今天咱们深入拆解面向对象编程&#xff08;OOP&#xff09;的三大核心特性之一——继承。作为Java开发的基础重点&#xff0c;继承不仅能帮我们实现代码复用、简化开发&#xff0c;更是后续理解多态、抽象类、接口的关键前提。不管你…...

火影AI绘画实战:用忍者绘卷Z-Image Turbo生成鸣人、佐助角色图教程

火影AI绘画实战&#xff1a;用忍者绘卷Z-Image Turbo生成鸣人、佐助角色图教程 1. 教程概述与准备工作 如果你是火影忍者的粉丝&#xff0c;现在可以通过AI技术轻松生成你最喜欢的角色图像。本教程将带你使用"忍者绘卷Z-Image Turbo"这个专门为火影风格优化的AI绘画…...

3大核心功能解放明日方舟玩家双手:MAA自动化助手全攻略

3大核心功能解放明日方舟玩家双手&#xff1a;MAA自动化助手全攻略 【免费下载链接】MaaAssistantArknights 《明日方舟》小助手&#xff0c;全日常一键长草&#xff01;| A one-click tool for the daily tasks of Arknights, supporting all clients. 项目地址: https://gi…...

从拆解到驱动:手把手教你用IMX6ULL驱动OV5640摄像头模块(附完整代码)

从拆解到驱动&#xff1a;手把手教你用IMX6ULL驱动OV5640摄像头模块&#xff08;附完整代码&#xff09; 1. 硬件连接与接口解析 OV5640作为一款500万像素的CMOS图像传感器&#xff0c;支持DVP和MIPI两种接口模式。在IMX6ULL平台上&#xff0c;我们选择使用DVP并行接口进行连接…...

AI艺术创作大赛:Shadow Sound Hunter生成作品展示

AI艺术创作大赛&#xff1a;Shadow & Sound Hunter生成作品展示 1. 引言 最近参加了一场AI艺术创作大赛&#xff0c;用Shadow & Sound Hunter模型生成了不少有意思的作品。这个模型在数字绘画、诗歌创作和音乐编曲方面都表现出色&#xff0c;让我看到了AI在艺术创作领…...

告别重复造轮子:用快马AI一键生成openclaw项目高效串口调试工具

在机器人开发过程中&#xff0c;串口通信是最基础也最频繁使用的功能之一。无论是传感器数据采集、电机控制指令下发&#xff0c;还是与各种硬件模块的交互&#xff0c;都离不开串口通信的支持。然而每次新项目都要从头实现串口通信功能&#xff0c;不仅浪费时间&#xff0c;还…...

别再用Delay了!用GD32的TIMER5实现精准1ms定时,让你的嵌入式程序更高效

告别阻塞式延时&#xff1a;用GD32 TIMER5构建高效嵌入式系统心跳 在嵌入式开发中&#xff0c;时间管理如同系统的心跳&#xff0c;决定了整个应用的响应速度和执行效率。许多开发者习惯使用delay_ms()这类阻塞式延时函数&#xff0c;却不知这会让CPU陷入无意义的等待状态&…...

Evolutionary Architecture by Example:如何避免过度工程化陷阱

Evolutionary Architecture by Example&#xff1a;如何避免过度工程化陷阱 【免费下载链接】evolutionary-architecture-by-example Navigate the complex landscape of .NET software architecture with our step-by-step, story-like guide. Unpack the interplay between m…...

大模型风口已至!普通人如何逆袭拿高薪?学员真实案例告诉你答案!

在人工智能飞速发展的今天&#xff0c;大模型已成为科技行业的核心赛道&#xff0c;无数人渴望抓住这波风口实现职业跃迁。而我们的大模型学员&#xff0c;用一份份亮眼的 offer&#xff0c;交出了完美答卷&#xff01; &#x1f31f; 平凡起点&#xff0c;非凡逆袭 他们中有**…...