本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路分析

阅读题目，得到关键信息首先是按照单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
首先采用 HashMap 结构统计单词频率。TOP K 问题，一般采用 heap 结构来进行排序。Java 中比较常用的是 PriorityQueue。为什么使用 PriorityQueue 呢？这里简单的介绍一下：

An unbounded priority queue based on a priority heap. 
The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
A priority queue does not permit null elements.
复制代码

上面这段介绍来自于官方文档, 简明扼要介绍了 PriorityQueue 的重点。

更多的 PriorityQueue 介绍信息，可以参考官方文档
在下面的代码中，我自定义了 WordNumber 数据结构，来记录单词和出现的频率，帮助理清思路。
在 PriorityQueue 的应用中，重写了 Comparator 满足题意要求！

代码

class WordNumber {
    String word;
    Integer number;

    public String getWord() {
        return word;
    }

    public void setWord(String word) {
        this.word = word;
    }

    public Integer getNumber() {
        return number;
    }

    public void setNumber(Integer number) {
        this.number = number;
    }
}


public class DayCode {
    public static void main(String[] args) {
        String[] words = new String[]{
                "i", "love", "leetcode", "i", "love", "coding"
        };
        int k = 2;

        String[] words1 = new String[]{
                "a", "aa", "aaa"
        };
        int k1 = 1;
        List<String> ans = new DayCode().topKFrequent(words, k);
        System.out.println(ans.toString());

        List<String> ans1 = new DayCode().topKFrequent(words1, k1);
        System.out.println(ans1.toString());
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<WordNumber> priorityQueue = new PriorityQueue<>(
                new Comparator<WordNumber>() {
                    @Override
                    public int compare(WordNumber o1, WordNumber o2) {
                        if (o1.getNumber().equals(o2.getNumber())) {
                            return o1.getWord().compareTo(o2.getWord());
                        } else {
                            return o2.getNumber() - o1.getNumber();
                        }

                    }
                }
        );

        for (Map.Entry<String, Integer> i : map.entrySet()) {
            WordNumber WordNumber = new WordNumber();
            WordNumber.setWord(i.getKey());
            WordNumber.setNumber(i.getValue());
            priorityQueue.add(WordNumber);
        }

        List<String> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            WordNumber temp = priorityQueue.poll();
            ans.add(temp.getWord());
        }

        return ans;
    }
}
复制代码