题解 | #字符串出现次数的TopK问题#

统计频率 遇到的问题

 //这个统计不了，因为putIfAbsent这个函数遇到重复的key会舍弃新插入的值
map.putIfAbsent(strings[i],map.getOrDefault(strings[i],0)+1);
//而put的策略是 覆盖掉旧值
 map.put(strings[i],map.getOrDefault(strings[i],0)+1);

步骤：

1. 统计频率
2. 构建最小堆，保证只能插入k个元素
3. 输出堆顶，堆顶为最小值，需要倒序构建结果集

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) {
        
        // write code here
        String[][] strs = new String[k][2];
        if(strings.length == 0 || k == 0) return strs;
        //统计频率
        HashMap<String,Integer> map = new HashMap();
         for(int i=0;i<strings.length;i++){
          
            map.put(strings[i],map.getOrDefault(strings[i],0)+1);
     
        }
        Set<Map.Entry<String,Integer>> entr = map.entrySet();
        //构建小顶堆
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>((
            o1,o2) -> {
            int t = o1.getValue() - o2.getValue();
            if(t != 0) {
                return t;
            } else {
                return o2.getKey().compareTo(o1.getKey());
            }
        });
        //加入元素
        for(Map.Entry<String,Integer> i : entr) {
            queue.offer(i);
            if(queue.size() > k) {
                queue.poll();
            }
        }
        //倒序遍历，生成结果集
        for(int i = k - 1; i >= 0; i--) {
            Map.Entry<String,Integer> temp = queue.poll();
            strs[i][0] = temp.getKey();
            strs[i][1] = temp.getValue() + "";
        }
        return strs;
    }
}