当前位置: 首页 > 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 …...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

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

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

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...