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

（1）使用map记录字符的出现次数；

（2）使用小根堆保存前k的结果（满足要求时间复杂度nlogk的要求）；

注意：定义堆的比较器，除了要考虑字符串出现次数值的大小，当出现次数相同时，还要比较字符串的字典序

public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        String[][] res = new String[k][2];
        //记录字符出现次数
        HashMap<String,Integer> map = new HashMap<>();
        for(int i = 0; i < strings.length; i++){
            if(map.containsKey(strings[i])){
                map.put(strings[i], map.get(strings[i]) + 1);
            }else{
                map.put(strings[i], 1);
            }
        }
        //建立小根堆，自定义比较器(次数值value相同，比较key的字典序，不相同直接比较次数值value)
        PriorityQueue<Map.Entry<String,Integer>> pq = new PriorityQueue<>((o1,o2) -> o1.getValue().equals(o2.getValue()) ? o2.getKey().compareTo(o1.getKey()) : o1.getValue()-o2.getValue());
        int size = 0;
        //维护size为k的小根堆
        for(Map.Entry<String,Integer> m : map.entrySet()){
            if(size < k){
                pq.offer(m);
                size++;
            }
            //大于堆顶元素插入
            else if((m.getValue().equals(pq.peek().getValue()) ? pq.peek().getKey().compareTo(m.getKey()) : m.getValue() - pq.peek().getValue()) > 0){
                pq.poll();
                pq.offer(m);
            }
        }
        //取出堆中元素，从后向前放置
        for(int i = k - 1; i >= 0; i--){
            Map.Entry<String,Integer> entry =(Map.Entry)pq.poll();
            res[i][0] = entry.getKey();
            res[i][1] = String.valueOf(entry.getValue());
        }
        return res;
    }
}