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

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
        if (k == 0 || strings.length == 0 || strings == null) return new String[0][0];
        HashMap<String, Integer> hash = new HashMap<String, Integer>();
        //统计字符串出现的频率
        for (String s : strings)
            hash.put(s, hash.getOrDefault(s, 0) + 1);
        //构造大小为K的最小堆
        //Map.Entry方法，将哈希表中的行取出来，就是取出来一个键值对
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
        (a, b) -> {
            // 频率不相同时：频率升序（频率低的在堆顶，准备被踢出）
            if (!a.getValue().equals(b.getValue())) {
                return a.getValue() - b.getValue();
            }
            // 频率相同时：字典序降序（字典序大的在堆顶，准备被踢出）
            else {
                return b.getKey().compareTo(a.getKey());
            }
        }
        );

        // 遍历 HashMap，维护大小为 K 的堆
        // hash.entrySet()方法，将取出来的每一行键值对构造成一个数组
        for (Map.Entry<String, Integer> entry : hash.entrySet()) {
            pq.offer(entry);
            // 如果堆里元素超过 K 个，就把最弱的（堆顶）弹出去
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // 将堆里的元素取出来，放入结果数组
        // 因为堆顶是最后剩下的 K 个里最弱的，所以我们要倒序填充数组
        String[][] res = new String[k][2];
        for (int i = k - 1; i >= 0; i--) {
            Map.Entry<String, Integer> entry = pq.poll();
            res[i][0] = entry.getKey();
            res[i][1] = String.valueOf(entry.getValue());
        }

        return res;
    }
}