692. 前K个高频单词 使用最大堆还是最小堆

Question

对于topK问题，总有一个疑问，一般选用最小堆实现，节省空间，堆的大小只需要k个空间，但是要输出元素时，如果不排序，就不符合这个题目的要求，这个题目要求输出时要按照频率从大到小排序。如果再排序一次，总感觉怪怪的。但是如果使用最大堆实现，就浪费空间了，要把全部元素放入堆中，老师有没有更好的解决方案呢。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> queue = new PriorityQueue<>(k, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                if (map.get(s1).equals(map.get(s2))) {
                    return s2.compareTo(s1);
                }
                return map.get(s1).compareTo(map.get(s2));
            }
        });
        for (String key : map.keySet()) {
            if (queue.size() < k) {
                queue.add(key);
            } else if (queue.comparator().compare(key, queue.peek()) > 0) {
                queue.poll();
                queue.add(key);
            }
        }
        List<String> res = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            res.add(queue.poll());
        }
        //最小堆实现的频率是从小到大排序的，结果要求是从大到小排序
        Collections.reverse(res);
        return res;
    }
}

Answer 1

liuyubobobo 2019-06-14 02:22:52

取top k应该使用最小堆。不断去淘汰当前找到的top k中的“最小者”。

你的思路是没有问题的。最后如果要求从大到小排序，就是要做一遍reverse。不过reverse不是排序：）

继续加油！：）