每日一练: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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...

使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...