题目描述：给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
示例1：
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。
解题思路：考数据结构的一道题。题目要求统计词频，并且根据词频和字典顺序输出。统计词频可以用哈希表，按照词频和字典顺序排序可以用优先队列。优先队列可以实现小根堆。通过重写优先队列的比较器comparator，实现按照词频升序，字典降序来构建大小为k的小根堆，最后的List进行反转。
//按词频构建小根堆
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> map = new HashMap<>();
for(String s:words) map.put(s,map.getOrDefault(s,0)+1); //put自动覆盖
PriorityQueue<Object[]> q = new PriorityQueue<>(k,(a,b)->{
//构造比较器
int c1 = (Integer)a[0], c2 = (Integer)b[0];
//词频不同，根据词频升序
if(c1 != c2) return c1-c2;
//词频相同，按字典降序
String s1 = (String)a[1], s2 = (String)b[1];
return s2.compareTo(s1);
});
for(String s:map.keySet()){
int cnt = map.get(s);
if(q.size() < k) q.add(new Object[]{cnt,s}); //队列元素小于k个，直接入队
else{
Object[] peek = q.peek();
if(cnt > (Integer)peek[0]){
q.poll();
q.add(new Object[]{cnt,s});
}else if(cnt == (Integer)peek[0]){
String top = (String)peek[1];
if(s.compareTo(top)<0){
q.poll();
q.add(new Object[]{cnt,s});
}
}
}
}
List<String> ans = new ArrayList<>();
while(!q.isEmpty()) ans.add((String)q.poll()[1]);
Collections.reverse(ans); //反转list
return ans;
}
}
