每日一练:LeeCode-347. 前 K 个高频元素(中) - 【优先级队列】
本文是力扣LeeCode-347. 前 K 个高频元素 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。
给你一个整数数组 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 个高频元素的集合是唯一的
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
思路:
- 统计元素出现的频率 ---------> 使⽤map来进⾏统计
- 对元素的频率进行排序 ---------> 由于map的value频率排序完,没法再找到对应的key,所以应该使⽤⼀种 容器适配器 就是 优先级队列,针对这道题,使用优先级队列最优,快排也比不上。
- 找出前K个⾼频元素 ---------> 相比大顶堆需要所有元素都排序一遍,使用小顶堆只排序k个元素,性能更优。 因为要统计最⼤前k个元素,只有⼩顶堆每次将最⼩的元素弹出,最后⼩顶堆⾥积累的才是前k个最⼤元素。
优先级队列:优先级队列内部元素是⾃动依照元素的权值排列,优先级队列对外接⼝只是从队头取元素,从队尾添加元素,再⽆其他取元素的⽅式,看起来就是⼀个队列。默认使用大顶堆排序,若修改使用小顶堆排序,需要重写优先级队列的compare()方法。
class Solution {public int[] topKFrequent(int[] nums, int k) {// 使用map字典,统计每个元素出现的次数,元素为键,元素出现的次数为值Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){if(map.containsKey(nums[i])){map.put(nums[i],map.get(nums[i])+1);}else{map.put(nums[i],1);}}PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){// @Override:不写leeCode也可通过public int compare(Integer a,Integer b){return map.get(a)-map.get(b);}});// 遍历map,用最小堆保存频率最大的k个元素for(Integer key : map.keySet()){// if(pq.size()<k){// pq.add(key);// }else if(map.get(key)>map.get(pq.peek())){// pq.remove();// pq.add(key);// }pq.add(key);if(pq.size()>k){pq.remove();}}// 取出最小堆中的元素int[] res = new int[k];int j=0;while(!pq.isEmpty()){res[j++] = pq.remove();}return res;}
}
大家有更好的方法,请不吝赐教。
相关文章:
每日一练:LeeCode-347. 前 K 个高频元素(中) - 【优先级队列】
本文是力扣LeeCode-347. 前 K 个高频元素 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输…...
<蓝桥杯软件赛>零基础备赛20周--第11周--贪心
报名明年4月蓝桥杯软件赛的同学们,如果你是大一零基础,目前懵懂中,不知该怎么办,可以看看本博客系列:备赛20周合集 20周的完整安排请点击:20周计划 每周发1个博客,共20周。 在QQ群上答疑&#x…...
PowerShell Instal 一键部署TeamCity
前言 TeamCity 是一个通用的 CI/CD 软件平台,可实现灵活的工作流程、协作和开发实践。允许在您的 DevOps 流程中成功实现持续集成、持续交付和持续部署。 系统支持 Centos7,8,9/Redhat7,8,9及复刻系列系统支持 Windows 10,11,2012,2016,2019,2022高版本建议使用9系列系统…...
将“渴望“乐谱写入AT24C02并读出播放
#include <reg51.h> // 包含51单片机寄存器定义的头文件 #include <intrins.h> //包含_nop_()函数定义的头文件 #define OP_READ 0xa1 // 器件地址以及读取操作,0xa1即为1010 0001B #define OP_WRITE 0xa0 // 器件地址以及写…...
Vue独立组件开发-动态组件
文章目录 一、前言二、实现三、优化四、总结五、最后 一、前言 在开发中,你经常会遇到这么一种情况:根据条件动态地切换某个组件,或动态地选择渲染某个组件。 Vue 提供了另外一个内置的组件 <component> 和 is 特性,可以更…...
前端八股文(HTML篇)
目录 1.什么是DOCTYPE,有何用呢? 2.说说对html语义化的理解 3.src和href的区别? 4.title与h1的区别,b与strong的区别,i与em的区别? 5.什么是严格模式与混杂模式? 6.前端页面有哪三层构成,分…...
RivaGAN 水印项目
git地址 https://github.com/DAI-Lab/RivaGAN Dockerfile (/tools下文件为git下的文件) ############################################### # 使用 NVIDIA CUDA 10.0 开发环境作为基础镜像 FROM kaldiasr/kaldi:gpu-ubuntu18.04-cuda10.0 # 设置非交互式安装模式以避免某些命…...
Games101作业5
1.实现Renderer.cpp 中的 Render():为每个像素生成光线 这里你需要为每个像素生成一条对应的光 线,然后调用函数 castRay() 来得到颜色,最后将颜色存储在帧缓冲区的相 应像素中。 我们要做的就是将屏幕空间下的坐标最后转换到世界空间的坐标…...
Golang解决跨域问题【OPTIONS预处理请求】
Golang解决跨域问题 前置知识:跨域问题产生条件及原因 跨域是是因为浏览器的同源策略限制,是浏览器的一种安全机制,服务端之间是不存在跨域的。 所谓同源指的是两个页面具有相同的协议、主机和端口,三者有任一不相同即会产生跨域…...
复试 || 就业day05(2023.12.31)算法篇
文章目录 前言找不同最长回文串找到所有数组中消失的数字下一个更大元素 I键盘行 前言 💫你好,我是辰chen,本文旨在准备考研复试或就业 💫文章题目大多来自于 leetcode,当然也可能来自洛谷或其他刷题平台 💫…...
Spring-4-代理
前面提到过,在Spring中有两种类型的代理:使用JDK Proxy类创建的JDK代理以及使用CGLIB Enhancer类创建的基于CGLIB的代理。 你可能想知道这两种代理之间有什么区别,以及为什么 Spring需要两种代理类型。 在本节中,将详细研究代理…...
设计模式:抽象工厂模式(讲故事易懂)
抽象工厂模式 定义:将有关联关系的系列产品放到一个工厂里,通过该工厂生产一系列产品。 设计模式有三大分类:创建型模式、结构型模式、行为型模式 抽象工厂模式属于创建型模式 上篇 工厂方法模式 提到工厂方法模式中每个工厂只生产一种特定…...
C语言中的Strict Aliasing Rule
文章目录 前言没有警告不代表没有问题目前的应对方法 前言 很久没写了,水一篇。 最近有个代码在gcc 4.8.5上编译失败。编译失败的提示是: error: dereferencing type-punned pointer will break strict-aliasing rules [-Werrorstrict-aliasing]查了下…...
单字符检测模型charnet使用方法,极简
Git链接 安装按照上面的说明,说下使用。 把tools下面的test做了一点修改,可以读取一张图片,把里面的单个字符都检测和识别出来。 然后绘制到屏幕上。 import torch from charnet.modeling.model import CharNet import cv2, os import num…...
Erlang、RabbitMQ下载与安装教程(windows超详细)
目录 安装Erlang 1.首先安装RabbitMQ需要安装Erlang环境 2.点击下载好的.exe文件进行傻瓜式安装,一直next即可 3.配置Erlang环境变量 安装RabbitMQ 1.给出RabbitMQ官网下载址:Installing on Windows — RabbitMQ,找到 2.配置RabbitMQ环境变量࿰…...
2023年终总结丨很苦,很酷!
文章目录 个人简介丨了解博主写在前面丨博主介绍年终总结丨博主成就年终总结丨博主想说年终总结丨学习芝士年终总结丨未来展望写在后面丨新年快乐 个人简介丨了解博主 主页地址:https://blog.csdn.net/m0_68111267 荣誉身份 ⭐2022年度CSDN 社区之星 Top6 ⭐2023年…...
鸿蒙 DevEco Studio 3.1 入门指南
本文主要记录开发者入门,从软件安装到项目运行,以及后续的学习 1,配置开发环境 1.1 下载安装包 官网下载链接 点击立即下载找到对应版版本 下载完成,按照提示默认安装即可 1.2 下载SDK及工具链 运行已安装的DevEco Studio&…...
ubuntu多用户环境dockerbug,卸载重装docker流程
之前不小心误操作删除重装docker,结果删除没成功,更没法重装,每次apt install都会报一个docker错误,虽然不影响软件的常规安装~但是现在还是需要装一个完整docker,还是选择删除一下,重点是关闭服…...
微信小程序开发系列-09自定义组件样式特性
微信小程序开发系列目录 《微信小程序开发系列-01创建一个最小的小程序项目》《微信小程序开发系列-02注册小程序》《微信小程序开发系列-03全局配置中的“window”和“tabBar”》《微信小程序开发系列-04获取用户图像和昵称》《微信小程序开发系列-05登录小程序》《微信小程序…...
数据结构 模拟实现LinkedList单向不循环链表
目录 一、链表的简单介绍 二、链表的接口 三、链表的方法实现 (1)display方法 (2)size得到单链表的长度方法 (3)addFirst头插方法 (4)addLast尾插方法 (5…...
OpenClaw 深度研究报告:从开源框架到企业级智能体平台的演进之路
一、核心定位:突破"对话天花板"的执行中枢 OpenClaw(外号"龙虾") 是由奥地利工程师 Peter Steinberger 于 2025 年底开发的本地优先、模型无关的 AI 智能体运行框架。其核心价值主张极为鲜明: “The AI that …...
终极指南:如何用Vortex模组管理器轻松管理250+游戏模组
终极指南:如何用Vortex模组管理器轻松管理250游戏模组 【免费下载链接】Vortex Vortex: Nexus-Mods开发的游戏模组管理器,用于简化模组的安装和管理过程。 项目地址: https://gitcode.com/gh_mirrors/vor/Vortex 还在为游戏模组安装繁琐、冲突不断…...
Phi-4-mini-reasoning应对软件测试:自动生成测试用例与缺陷分析
Phi-4-mini-reasoning应对软件测试:自动生成测试用例与缺陷分析 1. 引言:软件测试的痛点与AI解决方案 在软件开发的生命周期中,测试环节往往占据30%-50%的项目时间。传统测试工作面临两大核心挑战:一是测试用例设计需要大量人工…...
JETSON平台SDKManager一站式部署指南:从刷机到外置存储系统迁移
1. 开箱即用:JETSON开发板基础准备 刚拿到JETSON开发板时,很多开发者会对着这块巴掌大的硬件发懵。以我经手过的几十块JETSON TX2 NX为例,正确的开箱姿势应该是先检查配件完整性。除了开发板本体,你还需要准备: 5V/4…...
Pixel Couplet Gen 生成效果对比分析:不同参数下的对联质量评估
Pixel Couplet Gen 生成效果对比分析:不同参数下的对联质量评估 1. 引言:当AI遇上传统对联 春节贴对联是中国延续千年的文化传统,但创作一副既工整又有新意的对联并非易事。Pixel Couplet Gen作为一款AI对联生成工具,通过调整Te…...
OneMore插件终极指南:160+功能免费解锁OneNote完整生产力
OneMore插件终极指南:160功能免费解锁OneNote完整生产力 【免费下载链接】OneMore A OneNote add-in with simple, yet powerful and useful features 项目地址: https://gitcode.com/gh_mirrors/on/OneMore OneMore是一款功能强大的OneNote免费开源插件&…...
终极音乐解锁方案:在浏览器中实现加密音乐文件高效转换完整指南
终极音乐解锁方案:在浏览器中实现加密音乐文件高效转换完整指南 【免费下载链接】unlock-music 在浏览器中解锁加密的音乐文件。原仓库: 1. https://github.com/unlock-music/unlock-music ;2. https://git.unlock-music.dev/um/web 项目地…...
终极Win11Debloat优化指南:简单4步让你的Windows 11飞起来
终极Win11Debloat优化指南:简单4步让你的Windows 11飞起来 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutter an…...
Bootstrap4 导航栏详解
Bootstrap4 导航栏详解 引言 Bootstrap 是一个流行的前端框架,它为开发者提供了丰富的组件和工具,以快速构建响应式、移动优先的网站和应用程序。导航栏是网站的重要组成部分,它能够帮助用户轻松地在网站的不同页面之间导航。Bootstrap4 提供…...
护士执业资格考试历年真题及答案解析电子版PDF(2011-2025年)
2026年护士执业资格考试时间为2026年4月11-12日。为助力广大考生高效备考,小编精心整理了涵盖2011年至2025年的护士执业资格考试真题试卷及详细答案解析,包含《专业实务》和《实践能力》,高清PDF电子版,可打印,方便…...
