当前位置: 首页 > 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; 多媒体系统工程师系列【…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...