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

Leetcode 前 k 个高频元素

在这里插入图片描述

使用最小堆算法来解决这道题目:相当于有一个容量固定为K的教室,只能容纳 K 个人,学生们逐个逐个进入该教室,当教室容量达到K人之后,每次进入一个新的学生后,我们将分数最低的学生(类似本题中的频率最低元素)赶出去,最后所有学生都遍历结束之后,教室里所余的学生就是成绩前K高的学生们。

在这道题目中,最小堆(PriorityQueue)就像是一个只能容纳 K 个学生的教室,每次加入一个新的学生,教室满了就会将成绩最低的学生(即频率最低的元素)移除出去。最终剩下的 K 个学生,就是成绩最高的 K 个学生。

具体步骤如下:

  1. 我们先统计每个元素的出现频率(类似学生的分数)。
  2. 然后我们使用一个容量为 K 的最小堆来维护当前频率最高的 K 个元素。
    • 当堆的大小超过K时,将频率最低的元素移除,这样堆中始终只会保留频率最高的K个元素。
  3. 最后,堆中剩下的元素就是前K个高频元素。

这个方法的复杂度主要取决于建立和维护堆的过程,大概是O(N log K) 的时间复杂度,其中N是数组的长度,K是要返回的高频元素的个数。

class Solution {public int[] topKFrequent(int[] nums, int k) {//首先利用 Hashmap 统计每个数值的频率Map<Integer, Integer> freqMap = new HashMap<>();for(int num : nums) {freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);}//创建最小堆,存储键值对对象,key 代表元素,value 代表对应的频率值. // 比较器 (a, b) -> a.getValue() - b.getValue() 隐式地比较了两个元素的频率 // 如果 a 的值(频率)小于 b,则 a 会排在 b 前面(因为最小堆会将频率最小的元素放在堆顶)PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k, (a, b) -> a.getValue() - b.getValue());    //维护一个大小为 k 的最小堆for(Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {// 遍历插入一个新的键值对,而不是元素;键是唯一的,没有重复//由于堆顶元素始终是最小的元素,所以无论当前offer提供的待插入元素的大小与此时堆顶元素的大小如何,都会被插入堆中并自动调整。minHeap.offer(entry);if(minHeap.size() > k) { minHeap.poll(); }}int[] results = new int[k];for(int i = 0; i < k; ++i) {results[i] = minHeap.poll().getKey();}return results;}
}

相关文章:

Leetcode 前 k 个高频元素

使用最小堆算法来解决这道题目&#xff1a;相当于有一个容量固定为K的教室&#xff0c;只能容纳 K 个人&#xff0c;学生们逐个逐个进入该教室&#xff0c;当教室容量达到K人之后&#xff0c;每次进入一个新的学生后&#xff0c;我们将分数最低的学生(类似本题中的频率最低元素…...

[LeetCode] 面试题01.02 判定是否互为字符重拍

题目描述&#xff1a; 给定两个由小写字母组成的字符串 s1 和 s2&#xff0c;请编写一个程序&#xff0c;确定其中一个字符串的字符重新排列后&#xff0c;能否变成另一个字符串。 示例 1&#xff1a; 输入: s1 "abc", s2 "bca" 输出: true 示例 2&am…...

数据结构-4.5.KMP算法(旧版上)-朴素模式匹配算法的优化

朴素模式匹配算法最坏的情况&#xff1a; 一.实例&#xff1a; 第一轮匹配失败&#xff0c;开始下一轮的匹配&#xff1a; 不断的操作&#xff0c;最终匹配成功&#xff1a; 如上述图片所述&#xff0c;朴素模式匹配算法会导致时间开销增加&#xff0c; 优化思路&#xff1a;主…...

STM32 QSPI接口驱动GD/W25Qxx配置简要

STM32 QSPI接口GD/W25Qxx配置简要 &#x1f4dd;本篇会具体涉及介绍Winbond&#xff08;华邦&#xff09;和GD(兆易创新) NOR flash相关型号指令差异。由于网络上可以搜索到很多相关QSPI相关知识内容&#xff0c;不对QSPI通讯协议做深度解析。 &#x1f516;首先确保所使用的ST…...

UCI-HAR数据集深度剖析:训练仿真与可视化解读

在本篇文章中&#xff0c;我们将深入探讨如何使用Python对UCI人类活动识别&#xff08;HAR&#xff09;数据集进行分割和预处理&#xff0c;以及运用模型网络CNN对数据集进行训练仿真和可视化解读。 一、UCI-HAR数据集分析及介绍 UCI-HAR数据集是一个公开的数据集&#xff0c…...

牛客SQL练习详解 06:综合练习

牛客SQL练习详解 06&#xff1a;综合练习 SQL34 统计复旦用户8月练题情况SQL35 浙大不同难度题目的正确率SQL39 21年8月份练题总数 叮嘟&#xff01;这里是小啊呜的学习课程资料整理。好记性不如烂笔头&#xff0c;今天也是努力进步的一天。一起加油进阶吧&#xff01; SQL34 统…...

k8s apiserver高可用方案

目前官方推荐有 2 种方式部署k8s apiserver 高可用 keepalived and haproxy 部署有2种方式&#xff0c;一种是systemd管理的&#xff0c;另一种是pod形式&#xff0c;使用那种可以根据实际情况选择 服务部署 systemd方式 可以通过包管理工具安装&#xff0c;正常启动之后&…...

服务器数据恢复—硬盘坏扇区导致Linux系统服务器数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 一台linux操作系统网站服务器&#xff0c;该服务器上部署了几十个网站&#xff0c;使用一块SATA硬盘。 服务器故障&原因&#xff1a; 服务器在工作过程中突然宕机。管理员尝试重新启动服务器失败&#xff0c;于是将服务器上的硬盘拆下检测…...

【多线程】多线程(12):多线程环境下使用哈希表

【多线程环境下使用哈希表&#xff08;重点掌握&#xff09;】 可以使用类&#xff1a;“ConcurrentHashMap” ★ConcurrentHashMap对比HashMap和Hashtable的优化点 1.优化了锁的粒度【最核心】 //Hashtable的加锁&#xff0c;就是直接给put&#xff0c;get等方法加上synch…...

轻量服务器和云服务器ecs哪个好用一些?

轻量服务器和云服务器ecs哪个好用一些&#xff1f;轻量服务器与云服务器ECS在多方面存在显著差异&#xff0c;对于需要高性能计算和大规模数据处理的用户来说&#xff0c;ECS可能是更好的选择&#xff1b;而对于预算有限且需求较为简单的用户来说&#xff0c;轻量服务器可能更为…...

【交通标志识别系统】Python+卷积神经网络算法+人工智能+深度学习+机器学习+算法模型

一、介绍 交通标志识别系统。本系统使用Python作为主要编程语言&#xff0c;在交通标志图像识别功能实现中&#xff0c;基于TensorFlow搭建卷积神经网络算法模型&#xff0c;通过对收集到的58种常见的交通标志图像作为数据集&#xff0c;进行迭代训练最后得到一个识别精度较高…...

特种设备作业叉车司机试题附答案

1.发生事故要本着"&#xff08; &#xff09;不放过"的原则,查明原因、分清责任、严肃处理。 A.三 B.四 C.五 答案:B 2.柴油发动机在压缩行程终了时气体的温度和压力都比汽油机&#xff08; &#xff09;。 A.低 B.高 C.相同 答案:B 3.柴油发动机的压缩比比汽…...

【Nginx系列】Nginx启动失败

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

2024/10/12 计组大题专训

2018&#xff1a; 2019&#xff1a; 2020&#xff1a; 2021&#xff1a;...

2024年腾讯外包面试题(微创公司)

笔试&#xff1a; 1、判断异步执行顺序 console.log(1);setTimeout(()>{Promise.resolve().then(()>{console.log(2);})console.log(3);},0);new Promise ((resolve)>{for(let i0; i<1000;i ){if(i1000){resolve();}}console.log(4);}).then(()>{console.log(5…...

nginx运行时报:No rule to make target ‘build‘, needed by ‘deault‘.Stop

项目场景&#xff1a; 部署前端项目&#xff0c;将打好的前端包&#xff0c;放到服务器上&#xff0c;运行nginx执行&#xff0c;结果nginx运行报错。 问题描述 nginx运行报以下错误&#xff1a; No rule to make target ‘build‘, needed by ‘deault‘.Stop原因分析&…...

dvwa:暴力破解、命令注入、csrf全难度详解

暴力破解 easy模式 hydra -L /usr/share/wordlists/SecLists-master/Usernames/top-usernames-shortlist.txt -P /usr/share/wordlists/SecLists-master/Passwords/500-worst-passwords.txt 192.168.72.1 http-get-form "/dvwa/vulnerabilities/brute/:username^USER^&…...

Java-学生管理系统[初阶]

这次我们来尝试使用Java实现一下"学生管理系统"&#xff0c;顾名思义&#xff0c;就是实现一个能用来管理学生各种数据的系统。在后续学习中我们将对"学生管理系统"进行两种实现&#xff1a; &#x1f4da; 学生管理系统[初阶](不带模拟登录系统) &#…...

微信小程序 详情图片预览功能实现详解

详情图片预览功能实现详解 在开发微信小程序时&#xff0c;我们经常需要实现点击商品图片进行全屏预览的功能。这不仅提升了用户体验&#xff0c;还允许用户进行保存图片、发送给朋友等操作。本文将详细介绍如何实现这一功能。 思路分析 当用户在商品详情页点击图片时&#…...

LeetCode 48 Rotate Image 解题思路和python代码

题目&#xff1a; You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and …...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...