[Leetcode] 0703.数据流中的第K大元素

news/2024/2/29 3:07:44

703. 数据流中的第 K 大元素

点击上方标题跳转至leetcode

题目描述

设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。

请实现 KthLargest 类:

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val)val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。

示例:

输入:
["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);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

提示:
  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104
  • 题目数据保证,在查找第 k 大元素时,数组中至少有 k 个元素

解法

使用大小为 K 的小根堆,在初始化的时候,保证堆中的元素个数不超过 K 。
在每次 add() 的时候,将新元素 push() 到堆中,如果此时堆中的元素超过了 K,那么需要把堆中的最小元素(堆顶)pop() 出来。
此时堆中的最小元素(堆顶)就是整个数据流中的第 K 大元素。

Python3

class KthLargest:def __init__(self, k: int, nums: List[int]):self.q = []self.size = kfor num in nums:self.add(num)def add(self, val: int) -> int:heapq.heappush(self.q, val)# print(self.q)if len(self.q) > self.size:heapq.heappop(self.q)# print(self.q)return self.q[0]nums = [4,5,8,2]
k = 3
kthLargest = KthLargest(k, nums)
param_1 = kthLargest.add(3)
param_2 = kthLargest.add(5)
param_3 = kthLargest.add(10)
param_4 = kthLargest.add(9)
param_5 = kthLargest.add(4)print(param_1)
print(param_2)
print(param_3)
print(param_4)
print(param_5)

C++

#include<iostream>
#include<vector>
#include<queue>
using namespace std;class KthLargest {
public:priority_queue<int, vector<int>, greater<int>> q;int size;KthLargest(int k, vector<int>& nums) {size = k;for (int num : nums) add(num);}int add(int val) {q.push(val);if (q.size() > size) q.pop();return q.top();}
};int main(){vector<int> nums = {4,5,8,2};int k = 3;KthLargest* obj = new KthLargest(k, nums);int param_1 = obj->add(3);int param_2 = obj->add(5);int param_3 = obj->add(10);int param_4 = obj->add(9);int param_5 = obj->add(4);// int res1 = KthLargest(k,nums).add(3);cout << param_1 << "\t" << param_2 << "\t"  << param_3 << "\t"  << param_4 << "\t"  << param_5 << "\t" << endl;delete obj;return 0;
}
//g++ 703.cpp -std=c++11

时间复杂度:

初始化时间复杂度为:O(nlogk) ,其中 n 为初始化时 nums 的长度;
单次插入时间复杂度为:O(logk)
空间复杂度:O(k)需要使用优先队列存储前 k 大的元素;


http://www.ppmy.cn/news/62388.html

相关文章

知识推理——CNN模型总结

记录一下我看过的利用CNN实现知识推理的论文。 最后修改时间&#xff1a;2023.05.08 目录 1.ConvE 1.1.解决的问题 1.2.优势 1.3.贡献与创新点 1.4.方法 1.4.1 为什么用二维卷积&#xff0c;而不是一维卷积&#xff1f; 1.4.2.ConvE具体实现 1.ConvE 论文&#xff1a…

干货分享|一款让企业知识管理变得简单高效的工具软件

互联网发展到下半场&#xff0c;很多企业都开始进行数字化转型&#xff0c;在这个过程中&#xff0c;很多企业都忽视了极为重要的一点——企业的知识管理。如今信息化的时代&#xff0c;可以说企业的知识管理是引领企业数字化转型、进行创新的关键。 企业知识管理的实质就是对…

【shell脚本】函数

函数 一、shell函数1.1函数的定义1.3 函数返回值1.4函数传参1.5递归的使用 二、实验2.1实验一2.2实验二2.3实验三 一、shell函数 使用函数可以避免代码重复使用函数可以将大的过程风为若干个小的功能模块&#xff0c;代码的可读性更强 1.1函数的定义 【1】 function 函数名 …

JAVA中的异常处理机制是怎样的?

在 Java 中&#xff0c;异常处理机制是一种可以使程序在出现错误时进行自我修复的机制。Java 的异常处理机制可以通过抛出异常和捕获异常来实现。当一个异常被抛出时&#xff0c;程序会停止运行并输出异常信息&#xff0c;如果在代码中合适的位置进行捕获并处理异常&#xff0c…

[Tool] python项目中集成使用Firebase推送功能

背景介绍 目前&#xff0c;App推送功能已经非常普遍&#xff0c;几乎所有App都有推送功能。推送功能可以自己实现&#xff0c;也可以使用第三方提供的推送服务&#xff08;免费的收费的都有&#xff09;。本文主要介绍使用Firebase提供的推送服务Firebase Cloud Messaging&…

Python进阶——实现人脸识别

前言 嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 今天我们来实现一下人脸识别~ 先问大家一个问题 什么是百度Aip模块&#xff1f; 百度AI平台提供了很多的API接口供开发者快速的调用运用在项目中 本文写的是使用百度AI的在线接口SDK模块&#xff08;baidu-aip&#…

【2023年Mathorcup杯数学建模竞赛C题】电商物流网络包裹应急调运与结构优化--完整作品分享

1.问题背景 2.论文摘要 为了应对电商物流网络中物流场地和线路电商物流网络中物流场地和线路上货量波动的情况&#xff0c; 设计合理的物流网络调整方案以保障物流网络的正常运行。本文运用 0-1 整数规划模型&#xff0c;多目标动 态规划模型&#xff0c;给出了问题的结果。 针…

LLMs 记忆体全新升级:六大新功能全面出击,用户体验值拉满!

LLMs 时代之下&#xff0c;CVP Stack 必不可少。 其中&#xff0c;C 代表以 ChatGPT 为代表的大模型&#xff0c;它在 AI 程序中充当中央处理器的角色&#xff1b;V 代表 Vector Database&#xff0c;即以 Zilliz Cloud 和 Milvus 为代表的向量数据库&#xff0c;为大模型提供知…

.net7 通过 JsonTranscoding 实现 gRPC 与 Web API 一鱼两吃

目标 在一个网站内&#xff0c;用一套proto即提供gPRC 调用&#xff0c;又提供 Web API 调用。 实现方法 根据微软官方James Newton King&#xff08;Newtonsoft.json 作者&#xff09;的文章&#xff0c;.net7 里面提供了 JsonTranscoding 特性&#xff0c;只需要三步&#x…

【Mybatis】增删改查

1.添加相应的jar包 2.创建持久化类 在src目录下创建一个名为com.mybatis.po的包 创建持久化类MyUser,包含三个属性&#xff08;uid,uname,usex) package com.mybatis.po; /***springtest数据库中user表的持久化类*/ public class MyUser {private Integer uid;//主键private…

MathType7简体中文版数学公式编辑器下载安装教程

MathType一款专业的数学公式编辑器&#xff0c;理科生专用的必备工具&#xff0c;可应用于教育教学、科研机构、工程学、论文写作、期刊排版、编辑理科试卷等领域。2018年2月&#xff0c;MathType 7简体中文版正式发布&#xff0c;给用户带来全新的体验。MathType 是Windows和M…

Python人工智能—线性回归

线性回归 输入 输出 0.5 5.0 0.6 5.5 0.8 6.0 1.1 6.8 1.4 7.0 ... y f(x)预测函数&#xff1a;y w0w1x x: 输入 y: 输出 w0和w1: 模型参数 所谓模型训练&#xff0c;就是根据已知的x和y&#xff0c;找到最佳的模型参数w0 和 w1&#xff0c;尽可…

代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II

代码随想录算法训练营day32 | 贪心算法&#xff1a;122.买卖股票的最佳时机II &#xff0c;55. 跳跃游戏&#xff0c;45.跳跃游戏II 122.买卖股票的最佳时机II55. 跳跃游戏45.跳跃游戏II 122.买卖股票的最佳时机II 教程视频&#xff1a;https://www.bilibili.com/video/BV1ev4…

极简Python--列表

列表 列表是有序的&#xff0c;可以通过下标来访问列表中元素&#xff0c;同一个列表中支持不同的数据类型&#xff0c;支持对元素进行增删改查的操作 创建列表 # 使用中括号创建列表 ls ["Python", 1989, True, {"version": 3.7}] # list(可迭代对象)…

【RDC2022纪念板】RT-Smart D1s上手

目录 环境准备开发板硬件介绍开发环境搭建烧录 环境准备 windows电脑&#xff08;用于烧录固件和串口日志查看&#xff09;Ubuntu虚拟机&#xff08;用于编译生成固件&#xff09;RDC2022纪念板TypeC数据线 开发板硬件介绍 开发板使用了全志科技的D1s芯片&#xff0c;全志RIS…

性能测试工程师岗分级(初中高/资深/专家)?提高性能测试的价值...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 性能测试岗位按照…

1688获取商品api接口

作为一名技术爱好者&#xff0c;我们总会遇到各种各样的技术问题&#xff0c;需要寻找合适的技术解决方案。而在互联网时代&#xff0c;我们可以快速通过搜索引擎获取丰富的技术资源和解决方案。然而&#xff0c;在不同的技术分享中&#xff0c;我们常常会遇到质量参差不齐的文…

虹科方案 | HK-TrueNAS:音频协作的理想存储

一、虹科HK-TRUENAS 非常适合 AVID PRO TOOLS™ 专业音频编辑和大多数媒体和娱乐 (M&E) 工作流程从录制开始&#xff0c;经过后期制作&#xff0c;最后进入播放。这一过程可能需要几个月的时间来拍摄一部大型的电影&#xff0c;也可能需要几个小时甚至几分钟的时间来播放最…

双向链表及双向链表的常见操作和用js封装一个双向链表

书接上回&#xff0c;上一篇文章讲了单向链表以及用 js 封装一个单向链表&#xff0c;所以这节将介绍双向链表以及用 js 封装一个双向链表。待会我也会继续在文章后面附上视频学习链接地址&#xff0c;大家想学习的可以去看看 一、认识双向链表 首先来认识一下什么是双向链表&…

OpenGL学习教程之 材质

材质 在真实世界里&#xff0c;每个物体会对光产生不同的反应。钢看起来比陶瓷花瓶更闪闪发光&#xff0c;一个木头箱子不会像钢箱子一样对光产生很强的反射。每个物体对镜面高光也有不同的反应。有些物体不会散射(Scatter)很多光却会反射(Reflect)很多光&#xff0c;结果看起来…
最新文章