首页 > 试题广场 >

字符串出现次数的TopK问题

[编程题]字符串出现次数的TopK问题
  • 热度指数：44903 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。
返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。
对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
比如"ah1x"小于"ahb"，"231"<”32“
字符仅包含数字和字母

数据范围：字符串数满足 ，每个字符串长度 ，
要求：空间复杂度 ，时间复杂度

示例1

输入

["a","b","c","b"],2

输出

[["b","2"],["a","1"]]

说明

"b"出现了2次，记["b","2"]，"a"与"c"各出现1次，但是a字典序在c前面，记["a","1"]，最后返回[["b","2"],["a","1"]]
示例2

输入

["123","123","231","32"],2

输出

[["123","2"],["231","1"]]

说明

 "123"出现了2次，记["123","2"]，"231"与"32"各出现1次，但是"231"字典序在"32"前面，记["231","1"]，最后返回[["123","2"],["231","1"]]
示例3

输入

["abcd","abcd","abcd","pwb2","abcd","pwb2","p12"],3

输出

[["abcd","4"],["pwb2","2"],["p12","1"]]

备注:
算法知识视频讲解
开通博客
头像 有名
发表于 2021-07-16 21:11:04
精华题解 方法一 思路 题目要求找出出现次数前k的字符串，最为简单的就是直接遍历数组统计每个字符串出现的次数，接着再降序排序输出前k的字符串。 具体步骤 首先判断k值是否为0，若为0，则直接返回一个空的String二维数组； k值大于0时，通过哈希计算每个字符串出现的次数； 借助JDK的比较器Colle 展开全文
去ta的博客 赞 (21) 回复(1) 收起
头像 子夜降晴空
发表于 2021-03-23 21:16:16
struct cmp { bool operator() (pair<string, int> &p1, pair<string, int> &p2) { return p1.second > p2.second || (p1.s 展开全文
去ta的博客 赞 (28) 回复(0) 收起
头像 小猪部落
发表于 2021-01-20 00:56:36
Java， 使用自定义的比较器实现 import java.util.*; public class Solution { /** * return topK string * @param strings string字符串一维数组 strings * @ 展开全文
去ta的博客 赞 (14) 回复(1) 收起
头像 Arthur118
发表于 2020-12-04 23:57:36
统计各个字符出现次数，使用Map 创建初始堆(大顶堆)，定义出现次数大的字符串较大，出现次数相同是自然序较前的串较大 依次去K个堆顶元素并调整堆 import java.util.*; public class Solution { /** * return topK str 展开全文
去ta的博客 赞 (9) 回复(4) 收起
头像 执子一白
发表于 2020-12-08 16:00:19
Top K 问题首先想到堆，这道题还好定制一个比较器 用 PriorityQueue 就可以了，不需要动态调整堆结构。所以不需要手写堆逻辑哈哈偷了个懒，其实建议还是自己实现一个堆比较扎实能加深一下印象。 import java.util.*; public class Solution { 展开全文
去ta的博客 赞 (8) 回复(2) 收起
头像 棒棒糖🍭201906101800876
发表于 2021-10-11 13:02:39
NC97 字符串出现次数的TopK问题 描述 给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。 返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。 对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 猫头鹰啊猫头鹰
发表于 2021-07-14 19:43:55
善用stream流，大大减少代码量 import java.util.*; import java.util.function.Function; import java.util.stream.Collectors; public class  展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 牛客670572580号
发表于 2021-09-20 02:08:07
# # return topK string # @param strings string字符串一维数组 strings # @param k int整型 the k # @return string字符串二维数组 # class Solution: def topKstrings(sel 展开全文
去ta的博客 赞 (4) 回复(2) 收起
头像 陈文泰
发表于 2021-08-09 10:46:32
看了一圈好像没有python的题解，这里补一个，搬运自：https://leetcode.com/problems/top-k-frequent-words/discuss/1383677/Python-O(nlogk)-using-priority-queue-and-magic-method。因 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 每天学习一点
发表于 2022-02-25 21:07:49
（1）使用map记录字符的出现次数； （2）使用小根堆保存前k的结果（满足要求时间复杂度nlogk的要求）； 注意：定义堆的比较器，除了要考虑字符串出现次数值的大小，当出现次数相同时，还要比较字符串的字典序 public class Solution { /** * retur 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 小陆要懂云
发表于 2021-08-24 17:29:33
优先队列出队的是当前优先级最高的元素，我们要做的是把出现次数多的留下，所以比较器要以次数少为优先级高，其逻辑与默认的less行为相反 vector<vector<string> > topKstrings(vector<string>& strin 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

哈希
难度：
121条回答 7355浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字符串出现次数的TopK问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号