牛客NC97 字符串出现次数的TopK问题【中等哈希+优先级队列 Java/Go】

news/2024/5/20 16:24:57

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/fd711bdfa0e840b381d7e1b82183b3ee

核心

	哈希，优先级队列

Java代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** return topK string* @param strings string字符串一维数组 strings* @param k int整型 the k* @return string字符串二维数组*/public String[][] topKstrings (String[] strings, int k) {//哈希 ,优先级队列Map<String, Integer> smap = new HashMap<>();for (String s : strings) {if (!smap.containsKey(s)) {smap.put(s, 0);}smap.put(s, smap.get(s) + 1);}PriorityQueue<Integer> pq1 = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer a, Integer b) {return b - a;}});Map<Integer, PriorityQueue<String>> pqm = new HashMap<>();Set<Integer> unique = new HashSet<>();for (String s : smap.keySet()) {int cnt = smap.get(s);if (!unique.contains(cnt)) {unique.add(cnt);pq1.add(cnt);pqm.put(cnt, new PriorityQueue<>());}pqm.get(cnt).add(s);}String[][] ans = new String[k][2];int prevcnt = pq1.poll();PriorityQueue<String> prevpq = pqm.get(prevcnt);int idx = 0;while (idx < k) {while (idx < k && prevpq.size() > 0) {String cur = prevpq.poll();ans[idx][0] = cur;ans[idx][1] = String.valueOf(prevcnt);idx++;}if (idx == k) break;prevcnt = pq1.poll();prevpq = pqm.get(prevcnt);}return ans;}
}

Go代码

package mainimport ("sort""strconv""strings"
)/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** return topK string* @param strings string字符串一维数组 strings* @param k int整型 the k* @return string字符串二维数组*/
func topKstrings(strings []string, k int) [][]string {//哈希，优先级队列smap := map[string]int{}for _, s := range strings {_, ok := smap[s]if !ok {smap[s] = 0}smap[s] = smap[s] + 1}times := []int{}pqm := map[int]*PQAsc{}unique := map[int]bool{}for k, v := range smap {_, ok := unique[v]if !ok {times = append(times, v)pqm[v] = &PQAsc{Arr: make([]string, 10), Size: 0}unique[v] = true}pqm[v].add(k) //k是字符串}ans := make([][]string, k)sort.Ints(times)idx := 0for i := len(times) - 1; i >= 0; i-- {curcnt := times[i]pq := pqm[curcnt]for idx < k && pq.Size > 0 {ans[idx] = make([]string, 2)ans[idx][0] = pq.remove()ans[idx][1] = strconv.Itoa(curcnt)idx++}}return ans
}// 上升堆  下标0也就是堆顶元素最小
type PQAsc struct {Arr  []stringSize int
}// 扩容代码
func (pq *PQAsc) ensurecap(cap int) {oldsize := len(pq.Arr)if oldsize >= cap {return}newsize := oldsize + oldsize>>1newarr := make([]string, newsize)for i := 0; i < oldsize; i++ {newarr[i] = pq.Arr[i]}pq.Arr = newarr}func (pq *PQAsc) add(s string) {pq.ensurecap(pq.Size + 1)pq.Arr[pq.Size] = spq.shiftup(pq.Size)pq.Size++
}// 上滤
func (pq *PQAsc) shiftup(idx int) {base := pq.Arr[idx]for idx > 0 {pid := (idx - 1) >> 1parent := pq.Arr[pid]/*如果字符串相等(s1 == s2)，则返回0如果字符串1大于字符串2(s1> s2)，则返回1。如果字符串1小于字符串2，则返回-1*/if strings.Compare(base, parent) >= 0 {break}pq.Arr[idx] = parentidx = pid}pq.Arr[idx] = base
}func (pq *PQAsc) remove() string {ans := pq.Arr[0]pq.Arr[0] = pq.Arr[pq.Size-1]pq.Size--pq.shiftdown(0)return ans
}// 下钻
func (pq *PQAsc) shiftdown(idx int) {half := pq.Size >> 1base := pq.Arr[idx]for idx < half {childidx := idx<<1 + 1right := childidx + 1child := pq.Arr[childidx]if right < pq.Size && strings.Compare(child, pq.Arr[right]) >= 0 {childidx = rightchild = pq.Arr[right]}if strings.Compare(base, child) <= 0 {break}pq.Arr[idx] = childidx = childidx}pq.Arr[idx] = base
}