58-Map和Set练习-LeetCode692前k个高频单词
题目
给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。
示例 1:
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 "i" 在 "love" 之前。
示例 2:
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词,
出现次数依次为 4, 3, 2 和 1 次。
注意:
1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]
进阶:尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
思路:
前k个高频元素
找大用小。
- 用Map扫描集合,将每个单词及出现的频率存入Map中。
- 声明一个基于最小堆的优先级队列,传入比较器。(题目要求:默认按出现频次大小排序,频次相同再按字典排序。用String默认的compareTo方法即可;String默认实现了Comparable,基于字母的字典序比较)
- 依次出队列,找到前k个高频单词。
代码
class Solution {public List<String> topKFrequent(String[] words, int k) {//1.扫描原数组,将每个单词及出现的次数存储在Map中Map<String, Integer> cnt = new HashMap<String, Integer>();for (String word : words) {cnt.put(word, cnt.getOrDefault(word, 0) + 1);}//2.扫描Map集合,将前k个出现频次最高的入优先级队列(最小堆)//向优先级队列中传入一个比较器PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {return entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();}});//将每一个字符串插入到优先队列中,如果优先队列的大小超过了 k,那么就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。for (Map.Entry<String, Integer> entry : cnt.entrySet()) {pq.offer(entry);if (pq.size() > k) {pq.poll();}}//3.依次出队列,找到前k个高频单词。List<String> ret = new ArrayList<String>();//取大用小,每次从最小堆中堆顶取,得到的前k个高频单词的频率是从小到大的while (!pq.isEmpty()) {ret.add(pq.poll().getKey());}//将ret集合进行反转,这样就实现找到前k个高频单词的频率是从大到小的Collections.reverse(ret);return ret;}
}
相关文章:
58-Map和Set练习-LeetCode692前k个高频单词
题目 给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。 示例 1: 输入: words ["i", "love", …...
线程生命周期及五种状态
文章目录一、线程生命周期及五种状态1、New(初始化状态)2、Runnable(就绪状态)3、Running(运行状态)4、Blocked(阻塞状态)5、Terminated(终止状态)二、线程基本方法1、线程等待(wait)2、线程睡眠(sleep)3、…...
OBCP第八章 OB运维、监控与异常处理-灾难恢复
灾难恢复是指当数据库中的数据在被有意或无意破坏后复原数据库所需要执行的活动 回收站:回收站在原理上说就是一个数据字典表,放置用户删除的数据库对象信息。用户删除的东西被放入回收站后,其实仍然占据着物理空间,除非您手动进…...
亚马逊云科技Serverless Data:数字经济下的创新动能
Serverless时代已经到来!企业的技术架构,总是伴随着不断增长的数据与日趋复杂的业务持续演进。如何通过构建更易用的技术架构来聚焦在业务本身,而不必在底层基础设施的管理上投入过多的精力,是数据驱动型企业需要思考的重要议题。…...
【Ruby学习笔记】15.Ruby 异常
Ruby 异常 异常和执行总是被联系在一起。如果您打开一个不存在的文件,且没有恰当地处理这种情况,那么您的程序则被认为是低质量的。 如果异常发生,则程序停止。异常用于处理各种类型的错误,这些错误可能在程序执行期间发生&…...
聊聊MySQL主从延迟
文章目录 MySQL 的高可用是如何实现的呢?二、什么是主备延迟?三、主备延迟常见原因1、备库机器配置差2、备库干私活3、大事务四、主库不可用,主备切换有哪些策略?1、可靠优先2、可用优先实验一实验二3、结论MySQL 的高可用是如何实现的呢? 高可用性(high availability,缩…...
【C++从0到1】19、C++中多条件的if语句
C从0到1全系列教程 1、多条件的if语句 语法: if (表达式一) { // 表达式一为真时执行的语句。 } else if (表达式二) {// 表达式二为真时执行的语句。 } else if (表达式三) {// 表达式三为真时执行的语句。 } …… else if (表达式n) {// 表达式n为真时执行的语句。…...
【多微电网】计及碳排放的基于交替方向乘子法(ADMM)的多微网电能交互分布式运行策略研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
Linux(centos7)安装防火墙firewalld及开放端口相关命令
安装firewalld 防火墙命令: yum install firewalld 安装完成,查看防火墙状态为 not running,即未运行,输入命令开启: 添加开放端口: 防火墙相关命令: 查看防火墙状态 systemctl status firewa…...
Linux部署.Net Core Web项目
本文主要记录我在Linux(Ubuntu)上部署.net core 的操作记录,也便于以后部署。 如对您有所帮助,不胜荣幸~ 文章目录前言一、准备工作1. 版本信息2. windows端web项目二、操作步骤1. Linux 配置 .net 运行环境1.1 查看最新 .net 运行环境的下载路径1.2 安装…...
【C++】STL之stack、queue的使用和模拟实现+优先级队列(附仿函数)+容器适配器详解
之前的一段时间,我们共同学习了STL中一些容器,如string、vector和list等等。本章我们将步入新阶段的学习——容器适配器。本章将详解stack、queue的使用和模拟实现优先级队列(附仿函数)容器适配器等。 目录 (一&…...
第⑦讲:Ceph集群RGW对象存储核心概念及部署使用
文章目录1.RadosGW对象存储核心概念1.1.什么是RadosGW对象存储1.2.RGW对象存储架构1.3.RGW对象存储的特点1.4.对象存储中Bucket的特性1.4.不同接口类型的对象存储访问对比2.在集群中部署RadosGW对象存储组件2.1.部署RGW组件2.2.集群中部署完RGW组件后观察集群的信息状态2.3.修改…...
从异步到promise
一,背景 1.1,js的单线程 这一切,要从js诞生之初说起,因为js是单线程的语言。 js单线程原因:作为浏览器脚本语言,JavaScript的主要用途是与用户互动,以及操作DOM。这决定了它只能是单线程&…...
Linux系统中进行JDK环境的部署
一、为什么需要部署JDK。 JDK:Java Development Kit,是用于Java语言开发的环境。 部署JDK不需要懂得Java语言,只需要掌握Linux相关命令即可。 二、部署版本与环境。 系统:安装在VMware环境下的CentOS7.6; JDK版本&a…...
Leetcode.1033 移动石子直到连续
题目链接 Leetcode.1033 移动石子直到连续 Rating : 1421 题目描述 三枚石子放置在数轴上,位置分别为 a,b,c。 每一回合,你可以从两端之一拿起一枚石子(位置最大或最小),并将其放入…...
【Java】在SpringBoot中使用事务注解(@Transactional)时需要注意的点
在SpringBoot中使用事务注解(Transactional)时需要注意的点Transactional是什么使用事务注解(Transactional)时需要注意的点Transactional是什么 Transactional是Spring框架提供的一个注解,用于声明事务边界和配置事务…...
找到序列最高位的1和最高位的0并输出位置
前言: 该题为睿思芯科笔试题,笔试时长20分钟。 题目描述 接口如下: module first_1_and_0#(parameter WIDTH 8 )(input [WIDTH-1:0] data_in ,input target ,output exist ,outpu…...
面试总结sdiugiho
一、进程与线程的区别 进程: 一个在内存中运行的应用程序,每个进程都有自己独立的一块内存空间,一个进程可以有多个线程; windows 任务管理器中 一个 exe 就是一个进程。 线程: 进程中的一个执行任务(控制…...
WIN10無法再使用 IE 瀏覽器打开网页解决办法
修改 Registry(只適用 Win10) 微軟已於 2023 年 2 月 14 日永久停用 Internet Explorer,會透過 Edge 的更新讓使用者開啟 IE 時自動導向 Edge,其餘如工作列上的圖示,使用的方法則是透過「品質更新」的 B 更新來達成&am…...
搭建SpringBoot和Mysql Demo
1. 引言 在上一篇文章中,介绍了如何搭建一个SpringBoot项目;本篇文章,在上一篇文章的基础上,接着介绍下怎样实现SpringBoot和MySQL的整合。在后端开发中,数据库开发是绕不开的话题,开发中很多的时间都是在…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
