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

思路

这个题目要求时间复杂度，想到用优先队列，超过k个可以出队列，保证了调整堆的时间为,再加上外层循环遍历一遍数组，时间复杂度正好满足要求。
要统计出现字符串的频率，我们可以用一个哈希表记录。
排序要实现按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。那么我们得自定义排序，根据数字我们制作小顶堆，因为只有大的在下面，到时元素个数大于k是，可以把出现频率小的出队列。
对于频率相同的，根据字典排序。

代码

import java.util.*;


public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    // 利用java的内部类定义一个节点，用于记录字符串及其出现的次数
    public static class Node{
        private String str; // 记录字符串
        private Integer count; // 记录字符串出现的次数
        public Node(String _str, Integer _count){ // 节点的有参构造
            this.str = _str;
            this.count = _count;
        }
    }
    public String[][] topKstrings (String[] strings, int k) {
        // 自定义排序
        PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>(){
            @Override
            public int compare(Node o1, Node o2){
                // java的优先队列底层就是小根堆，次数大的在下面
                if (o1.count > o2.count){
                    return 1;
                } else if (o1.count < o2.count){
                    return -1;
                } else {
                    // 频率相同，字典排序前要在下面
                    return o2.str.compareTo(o1.str);
                }
            }
        });
        HashMap<String, Integer> map = new HashMap<>();
        // 哈希表记录字符串及其频率
        for (String s : strings){
            map.put(s,map.getOrDefault(s,0)+1);
        }
        // 遍历哈希表
        for (Map.Entry<String, Integer> entry : map.entrySet()){
            String key = entry.getKey();
            Integer value = entry.getValue();
            queue.offer(new Node(key, value));
            // 队列中的元素大于k,及时出队列
            if (queue.size() > k){
                queue.poll();
            }
        }
        String[][] result = new String[k][2];
        // 遍历队列，加入结果数组
        for (int i = k - 1; i >= 0; i--){
            Node node = queue.poll();
            result[i][0] = node.str;
            result[i][1] = Integer.toString(node.count);
        }
        return result;
    }
}