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

1.将传入数组放入hashmap中统计出现次数
2.利用优先级队列来建立堆:需要注意的是优先级队列中元素默认以小根堆排序
    2.1将map中前k个元素填入优先级队列(默认小根堆)中
    2.2.如果map中剩余节点的num大于堆顶节点的num，入堆
3.将建立好的堆从后往前输出K个，即是最大的K个元素
ps:由于字母a,b,c..z的ascii值逐渐增大，所以想要字典排序,以a，b为例，即a在前面b在后面，就需要a<b,即a-b<0,后面重写compareTo会用到.

import java.util.*;
public class Solution {
    /**
     * return topK string
     *
     * @param strings string字符串一维数组 strings
     * @param k       int整型 the k
     * @return string字符串二维数组
     */
    public static String[][] topKstrings(String[] strings, int k) {
        if(strings==null || strings.length==0){
            return null;
        }
        // write code here
        PriorityQueue<MyNode> heap = new PriorityQueue<MyNode>();


        //传入统计后结果map
        HashMap<String, Integer> map = Statistical(strings);
        //map集合entryset
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        //入堆:实现小顶堆，输出到结果集就是堆的逆序，即大顶堆
        for (Map.Entry<String, Integer> entry : entries) {
            //将自己的节点放进堆中,以num小根形式
            MyNode node = new MyNode(entry.getKey(), entry.getValue());
            if (heap.size() < k) {
                heap.add(node);
            } else {
                if (heap.peek().compareTo(node)< 0) {//堆顶元素大小 小于 剩余节点
                    //删除堆顶元素
                    heap.poll();
                    //添加剩余元素
                    heap.offer(new MyNode(entry.getKey(), entry.getValue()));
                }
            }
        }

        String[][] res = new String[k][2];

        //从后往前输出最后K个堆节点
        for (int i = k-1; i >=0; i--) {
            MyNode node = heap.poll();
            res[i][0] = node.val;
            res[i][1] = String.valueOf(node.num);
        }
        return res;
    }

    //统计数组中字符出现次数
    public static HashMap<String, Integer> Statistical(String[] strings) {
        HashMap<String, Integer> countMap = new HashMap<>();
        for (String string : strings) {
            Integer value = countMap.get(string);
            if (value == null) {
                value = 0;
            }
            countMap.put(string, value + 1);
        }
        return countMap;
    }

//     public static void main(String[] args) {
//         String[] s = {"i", "i", "i", "W", "W", "W", "2"};
//         String[][] strings = topKstrings(s, 2);

//     }
     //自定义堆中节点结构，需要实现比较方法
    static class MyNode implements Comparable<MyNode> {
        String val;
        int num;

        MyNode(String val, int num) {
            this.num = num;
            this.val = val;
        }

        @Override
        public int compareTo(MyNode o) {
            if (this.num - o.num>0) {
                return 1;
            } else if(this.num - o.num<0){
                return -1;
            }else {
                //按照字典顺序排
                return o.val.compareTo(this.val);
            } 
        }
    }
}