目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
字符串出现次数的TopK问题
访问量:1168
一、简介
给定一个字符串数组,再给定整数 k ,请返回出现次数前k名的字符串和对应的次数。
返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率,按字典序排序。
对于两个字符串,大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
比如"ah1x"小于"ahb","231"<”32“
字符仅包含数字和字母
输入: ["a","b","c","b"],2 返回值: [["b","2"],["a","1"]] 说明: "b"出现了2次,记["b","2"],"a"与"c"各出现1次,但是a字典序在c前面,记["a","1"],最后返回[["b","2"],["a","1"]]
二、实现
思路1:先使用hash计算出每个字符串出现的次数,然后将hash转为数组,进行排序,最后输出k个数字即可
type MapNode struct { str string times int } /** * return topK string * @param strings string字符串一维数组 strings * @param k int整型 the k * @return string字符串二维数组 */ func topKstrings( strings []string , k int ) [][]string { // write code here if len(strings) == 0 { return nil } dataMap := make(map[string]int) // 用于统计每个字符串出现次数 for _,item := range strings { dataMap[item] = dataMap[item] + 1 } dataList := make([]MapNode, 0) // 为了排序方便,转为数组 for k,v := range dataMap { dataList = append(dataList, MapNode{ str:k, times:v, }) } // 排序数组 sort.Slice(dataList, func(i, j int) bool { if dataList[i].times == dataList[j].times { return dataList[i].str > dataList[j].str } return dataList[i].times < dataList[j].times }) // 输出倒数k个 rs := make([][]string, 0) var i = len(dataList) -1 for i >= 0 && k > 0{ rs = append(rs, []string{ dataList[i].str, fmt.Sprint(dataList[i].times), }) i-- k -- } return rs }
思路2:先使用hash计算出每个字符串出现的次数,然后以k个最大数构建最小堆,最后利用堆排序
/** * return topK string * @param strings string字符串一维数组 strings * @param k int整型 the k * @return string字符串二维数组 */ func topKstrings(strings []string, k int) [][]string { // write code here dataMap := make(map[string]int) for _, item := range strings { dataMap[item] = dataMap[item] + 1 } // 以最大的k个数,构建最小堆 strList := make([]string, 0) for str := range dataMap { if len(strList) < k { strList = append(strList, str) if len(strList) == k { // 构建最小堆 index := len(strList)/2 - 1 for index >= 0 { jumpHeap(index, strList, dataMap) index-- } } continue } else if comp(str, strList[0], dataMap) { continue } else { strList[0] = str jumpHeap(0, strList, dataMap) } } // 将heap中的元素进行排序 rs := make([][]string, k) for i := 0; i < k; i++ { if len(strList) == 0 { break } rs[k - i -1] = []string{ strList[0], fmt.Sprint(dataMap[strList[0]]), } strList = strList[1:] // 再次构建堆 index := len(strList)/2 - 1 for index >= 0 { jumpHeap(index, strList, dataMap) index-- } } return rs } func jumpHeap(index int, data []string, dataMap map[string]int) { // 构建堆 leftIndex := 2*index + 1 rightIndex := 2*index + 2 if leftIndex >= len(data) { return } if rightIndex >= len(data) { if comp(data[index], data[leftIndex], dataMap) { return } data[index], data[leftIndex] = data[leftIndex], data[index] jumpHeap(leftIndex, data, dataMap) return } // 根节点为最小值 if comp(data[index], data[leftIndex], dataMap) && comp(data[index], data[rightIndex], dataMap) { return } // 左节点为最小值 if comp(data[leftIndex], data[index], dataMap) && comp(data[leftIndex], data[rightIndex], dataMap) { data[index], data[leftIndex] = data[leftIndex], data[index] jumpHeap(leftIndex, data, dataMap) return } // 右节点为最小值 data[index], data[rightIndex] = data[rightIndex], data[index] jumpHeap(rightIndex, data, dataMap) return } // 判断str1 是否小于 str2 func comp(str1, str2 string, dataMap map[string]int) bool { if dataMap[str2] == dataMap[str1] { return str1 <= str2 } return dataMap[str1] <= dataMap[str2] }
题目来源:牛客
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助