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

优先队列经典例题leetcode思路代码详解

目录

leetcode215题.数组中的第k个最大元素

leetcode347题.前k个高频元素

leetcode295题.数据流的中位数


对优先队列感兴趣的朋友可以去看我上一篇文章。

优先队列基础讲解-CSDN博客

leetcode215题.数组中的第k个最大元素

215. 数组中的第K个最大元素 - 力扣(LeetCode)

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104
class Solution {public int findKthLargest(int[] nums, int k) {// 默认是小根堆 复杂度 空间:O(k). 时间 nlogkQueue<Integer> minQueue = new PriorityQueue<>();for(int i = 0 ; i < nums.length; i++){if(minQueue.size() < k){minQueue.offer(nums[i]);}else if(minQueue.peek() < nums[i]){minQueue.poll();minQueue.offer(nums[i]);}}return minQueue.peek();}
}

leetcode347题.前k个高频元素

347. 前 K 个高频元素 - 力扣(LeetCode)

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示:

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
class Solution {public int[] topKFrequent(int[] nums, int k) {// 创建一个HashMap用于存储数字及其出现的频率Map<Integer,Integer> map = new HashMap<>();// 遍历输入数组,统计每个数字出现的次数for(int num:nums){map.put(num,map.getOrDefault(num,0)+1);}// 创建一个优先队列(最小堆),用于存储频率最高的k个数字PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){public int compare(Integer a,Integer b){// 比较两个数字的频率,频率高的排在前面return map.get(a) - map.get(b);}});// 遍历HashMap的键集,将前k个频率最高的数字添加到优先队列中for(Integer key:map.keySet()){if(queue.size() < k){queue.add(key);}else if(map.get(key) > map.get(queue.peek())){// 如果当前数字的频率大于优先队列中的最小频率,则替换最小频率的数字queue.poll();queue.add(key);}}// 创建一个长度为k的数组,用于存储结果int [] res = new int[k];int index = 0;// 从优先队列中依次取出元素,将其添加到结果数组中while(!queue.isEmpty()){res[index++] = queue.poll();}// 返回结果数组return res;}
}

leetcode295题.数据流的中位数

295. 数据流的中位数 - 力扣(LeetCode)

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder()初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1:

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -105 <= num <= 105
  • 在调用 findMedian 之前,数据结构中至少有一个元素
  • 最多 5 * 104 次调用 addNum 和 findMedian
class MedianFinder {//Queue<Integer> max;// 保存较小那部分,并且多保存一个Queue<Integer> min;// 保存较大那部分public MedianFinder() {max = new PriorityQueue<>((x,y)->(y - x));min = new PriorityQueue<>();}public void addNum(int num) {// 偶数if(max.size() == min.size()){min.offer(num);max.offer(min.poll());} else {max.offer(num);min.offer(max.poll());}}public double findMedian() {int size = max.size() + min.size();if(size % 2 == 1){return max.peek() * 1.0;}else{return (max.peek() + min.peek()) / 2.0;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

相关文章:

优先队列经典例题leetcode思路代码详解

目录 leetcode215题.数组中的第k个最大元素 leetcode347题.前k个高频元素 leetcode295题.数据流的中位数 对优先队列感兴趣的朋友可以去看我上一篇文章。 优先队列基础讲解-CSDN博客 leetcode215题.数组中的第k个最大元素 215. 数组中的第K个最大元素 - 力扣&#xff08;…...

新型Python环境与依赖管理工具——pipenv

文章目录 pipenv介绍pipenv安装pipenv使用创建虚拟环境删除虚拟环境安装依赖查看包之间的依赖图卸载依赖在虚拟环境中执行命令shell环境下通过requirements.txt安装依赖导出requirements.txt文件查看虚拟环境的路径 pipenv介绍 pipenv可以看做是pip和virtualenv的组合体&#…...

FastDFS+Nginx - 本地搭建文件服务器同时实现在外远程访问「内网穿透」

文章目录 前言1. 本地搭建FastDFS文件系统1.1 环境安装1.2 安装libfastcommon1.3 安装FastDFS1.4 配置Tracker1.5 配置Storage1.6 测试上传下载1.7 与Nginx整合1.8 安装Nginx1.9 配置Nginx 2. 局域网测试访问FastDFS3. 安装cpolar内网穿透4. 配置公网访问地址5. 固定公网地址5.…...

kendo-splitter动态分配分隔框大小

通过size方法&#xff0c;动态改变框大小&#xff0c;参考链接&#xff1a;https://docs.telerik.com/kendo-ui/api/javascript/ui/splitter/methods/size vue画面 <kendo-button type"primary" click"changePane">button</kendo-button><…...

网站提示不安全?

随着互联网的普及和发展&#xff0c;网络安全问题日益严重。黑客攻击、数据泄露、恶意软件等问题层出不穷&#xff0c;给企业和个人带来了巨大的损失。在这个背景下&#xff0c;确保网站安全显得尤为重要&#xff0c;而使用SSL证书是解决这些问题的有效措施。 什么是SSL证书&am…...

C# 泛型编译特性对性能的影响

C#作为一种强类型语言&#xff0c;具有丰富的泛型支持&#xff0c;允许开发者编写可以应对不同数据类型的通用代码。然而&#xff0c;在泛型编译时&#xff0c;针对结构和类作为泛型参数时&#xff0c;会对性能产生不同的影响。 泛型编译行为 在C#中&#xff0c;泛型编译行为取…...

11-30 JavaWeb

修改与删除操作 防止空指针异常 localhost:8080 -> 分页查询 修改流程&#xff1a;(先查后改(两个servlet)) 修改&#xff1a; 传用户id(用户id怎么得到 -> 循环一次得到一个user 对象 user对象里用user.getId()得到用户id) UpdateUserQueryServlet.java &#xff08;…...

LCR 047. 二叉树剪枝 和 leetCode 1110. 删点成林 + 递归 + 图解

给定一个二叉树 根节点 root &#xff0c;树的每个节点的值要么是 0&#xff0c;要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。节点 node 的子树为 node 本身&#xff0c;以及所有 node 的后代。 示例 1: 输入: [1,null,0,0,1] 输出: [1,null,0,null,1] 解释: 只有红…...

Flutter笔记:路由观察者

Flutter系列 路由观察者 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/134572181 目 录 1. 概述2. 路由…...

【驱动】串口驱动分析(三)-serial driver

简介 前两节我们介绍串口驱动的框架和tty core部分。这节我们介绍和硬件紧密相关的串口驱动部分。 UART驱动部分依赖于硬件平台&#xff0c;而TTY驱动和具体的平台无关。虽然UART部分依赖于平台&#xff0c;但是不管是哪个硬件平台&#xff0c;驱动的思路都是一致的&#xff…...

(C++20) constinit常量初始化

文章目录 由来constinit 常量初始化常量初始化 ! 初始化常量初始化声明静态存储对象非初始化声明thread_local END 由来 在C多文件编译中会出现一个常见的问题&#xff0c;叫做静态初始化顺序问题。Static Initialization Order Fiasco。 比如现在有两个文件&#xff0c;其中…...

python实现获取aws route53域名信息

最近由于工作原因接触到aws的服务&#xff0c;我需要实时获取所有的域名信息&#xff0c;用于对其进行扫描&#xff0c;因此写了一个自动化爬取脚本 给需要的人分享。 1.基础准备 代码环境&#xff1a;python3 第三方库&#xff1a;boto3 &#xff08;安装方法pip install…...

Linux_Linux终端常用快捷键

Linux命令行核心常用快捷键是一些在终端中使用的快捷键组合&#xff0c;用于提高命令行操作的效率。下面是这些快捷键的原理详细解释、使用场景解释 Ctrl A &#xff1a;将光标移动到命令行的开头。这个快捷键的原理是发送一个控制序列到终端&#xff0c;告诉终端将光标移动到…...

Neo4j 数据库管理 数据备份与恢复(头歌)

文章目录 第1关&#xff1a;数据备份与恢复任务描述相关知识数据备份数据导入 编程要求测试说明答案测试前准备Cypher 代码数据备份与导入 第1关&#xff1a;数据备份与恢复 任务描述 本关任务&#xff1a;熟练掌握数据备份与恢复。 相关知识 为了完成本关任务&#xff0c;…...

TCP传输的三次握手四次挥手策略

TCP传输的三次握手四次挥手策略如下&#xff1a; 第一次握手&#xff1a;客户端发送一个带有SYN标志的数据包给服务器&#xff0c;并记为SYN_Client。第二次握手&#xff1a;服务器收到SYN_Client后&#xff0c;向客户端发送一个带有SYN和ACK标志的数据包&#xff0c;记为SYN_…...

在gitlab上使用server_hooks

文章目录 1. 前置条件2. Git Hook2.1 Git Hook 分为两部分&#xff1a;本地和远程2.1.1 本地 Git Hook&#xff0c;由提交和合并等操作触发&#xff1a;2.1.2 远程 Git Hook&#xff0c;运行在网络操作上&#xff0c;例如接收推送的提交&#xff1a; 3. 操作步骤3.1 对所有的仓…...

【云原生系列】Kubernetes知识点

目录 概念 基础架构 单master节点 多master节点 组件 Master节点核心组件 其他组件 请求发送流程 插件 核心资源 调度资源 Pod 创建pod组件间调用流程 pod生命周期&#xff1a; 初始化容器 镜像拉取策略 重启策略 钩子函数 探针 探针的实现方式 DownwardAP…...

Hugging-Face报错锦囊(不断更新)

requests.exceptions.SSLError: (MaxRetryError(“HTTPSConnectionPool(host‘huggingface.co’, port443): Max retries exceeded with url: /api/models/bert-base-chinese (Caused by SSLError(SSLCertVerificationError(1, ‘[SSL: CERTIFICATE_VERIFY_FAILED] certificate…...

Redis核心数据结构

目录 五种基础数据结构 string hash list set zset 用zset实现微博热搜 scan遍历 高频问题 五种基础数据结构 string 单个赋值set 批量赋值/取值 msetmget 设置不存在字符串setnx, 如果不存在, 则设置成功返回1, 如果存在返回0, 可以当做分布式锁 删除值 设置过期时…...

Redis 如何批量删除指定前缀的Key

批量删除指定前缀的Key有两中方法&#xff0c;一种是借助 redis-cli&#xff0c;另一种是通过 SCAN 命令来遍历所有匹配前缀的 key&#xff0c;并使用 DEL 命令逐个删除它们。 redis-cli 使用 Redis 自带的 redis-cli 命令行工具&#xff0c;你可以通过以下方式批量删除指定前…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...