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

优先级队列PriorityQueue的队列头是按内部排序接口规则来说，最小的那个元素。
所以可以看作一个小顶堆，而要找到最大频率的k个字符串且按字典序排列，需要注意字符串String的compareTo方法返回的是ASCLL码(前减后)的差值，也就是字典序越靠前的越小，而我们们每次在小顶堆中删除堆顶时，想要删除的是频率最低或字典序最靠后的字符串，因此频率的排序就是正常的前减后，字符串的排序要让字典序靠后的排前面，所以是后compareTo前。这样建立的小顶堆维护了前k个要求的元素，但是放入数组时要注意堆顶是该放到数组末尾的，因为它的频率最低和字典序最靠后，下面的元素也是出堆逆序入数组。

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
        HashMap<String,Integer>sc=new HashMap<>();
        for(String s:strings){
            sc.put(s,sc.getOrDefault(s,0)+1);
        }
        PriorityQueue<String>heap=new PriorityQueue<>(
            //自定义Comparable接口
            (a,b)->sc.get(a).equals(sc.get(b))?b.compareTo(a):sc.get(a)-sc.get(b));
        for(String s:sc.keySet()){
            heap.offer(s);
            //出堆的是“最不满足要求”的元素
            if(heap.size()>k)heap.poll();
        }
        String[][]res=new String[k][2];
        int j=k-1;
        while(!heap.isEmpty()){
            //出堆并逆序放入数组
            String tmp=heap.poll();
            res[j][0]=tmp;
            res[j][1]=sc.get(tmp)+"";
            j--;
        }
        return res;
    }
}