前K个高频单词
692. 前K个高频单词 - 力扣（LeetCode）
解决这个问题我们先得知道每个单词出现的次数，用map存储下来，然后将出现次数最多的通过建立小根堆解决top-K问题 ，重点是top-K的求取。
1.建立map
首先我们可以先将这些单词的出现次数都通过map中的key和value记录下来。第一步先创建一个map
Map<String, Integer> map = new HashMap<>();2.将单词以及单词出现的次数存储到map中
在这里需要注意第一次出现的单词，第一次出现的单词没有对应的value值就会返回一个空指针null，往后再出现就直接在value中加1即可。
for (String word : words){
//为什么不直接在map的基础上加1呢？原因在于第一次记录某一个单词时get(word)会返回null（Integer类型的默认值就是null），如果为空就不能进行加1的操作并且报空指针异常
//map.put(word, map.get(word)+1);
//方法1，可以通过map中getOrDefault方法设置它的第一次出现
//map.put(word, map.getOrDefault(word,0)+1);
//方法2，通过if-else，当出现为空时，那就更新value值；不为空时就加1
if (map.get(word) == null){//如果这个单词在之前遍历时没有出现过，那就
map.put(word, 1);
}else{
map.put(word, map.get(word)+1);
}
}3.建立小根堆
要得到单词次数最多的前K个，就需要建立小根堆（在之前的优先级对列中已经讲过），会用到PriorityQueue。 建立小根堆需要上传一个比较器，这个比较器是将
//建立小根堆
PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return o1.getValue() - o2.getValue();
}
});4.遍历map，依次加入堆中
现在我们想想，要将单词加入堆中，可能会出现k大于words中所有单词的个数，这样就可以直接把所有单词都加入堆中；
if (minHeap.size() < k){
minHeap.offer(entry);
}剩下一种可能就是k<=words.length()，对于这个情况来说每次加入一个单词都需要进行比较，比较的情况也很多种。下面仔细的讲一下如果比较，首先我们需要知道在这个堆中的堆顶元素top，当加入的单词频率与top相同时，需要把top出队，然后让字母小的进来；还有就是可能会出现频率比top的大的情况，这种情况也需要先出队然后再进队。
else{
Map.Entry<String, Integer> top = minHeap.peek();
//频率相同时，也就是出现次数相同时
if (top.getValue().compareTo(entry.getValue()) == 0){
//字母小的先进来
if(top.getKey().compareTo(entry.getKey()) > 0){
//top的单词比进来的要大，所以top要出队,entry要进队
minHeap.poll();
minHeap.offer(entry);
}
}else{
//
if(top.getValue().compareTo(entry.getValue())<0){
minHeap.poll();
minHeap.offer(entry);
}
}5.依次讲堆中的单词放进List<String>类型中
List<String>类型，所以我们需要创建一个ArrayList类型的集合用于存放堆中单词，但是题目需要的是从大到小的单词频率，从堆中拿出来的是从小到大的，所以最后还需要逆序一遍顺序表。
List<String> ret = new ArrayList<>();
for (int i = 0; i < k; i++){
Map.Entry<String, Integer> top = minHeap.poll();
ret.add(top.getKey());
}
Collections.reverse(ret);
return ret;6.改进比较器
如果把以上全部代码放到在线OJ题中，会发现总有一个结过时不通过的。那为什么呢？主要在于如果k>所有单词的个数，那么在堆中就没有相同频率的比较，所以我们还需要在比较器中添加频率相同时需要建立一个大根堆。
PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
//当字母频率相同时，按照字母建立大根堆
if (o1.getValue().compareTo(o2.getValue()) == 0){
return o2.getKey().compareTo(o1.getKey());
}
return o1.getValue() - o2.getValue();
}
});以下是全部代码，大家可以参考一下哦~
public static List<String> topKFrequent(String[] words, int k) {//
HashMap<String, Integer> map = new HashMap<>();
for (String word : words){
//为什么不直接在map的基础上加1呢？原因在于第一次记录某一个单词时get(word)会返回null（Integer类型的默认值就是null），
//如果为空就不能进行加1的操作并且报空指针异常
//map.put(word, map.get(word)+1);
//方法1，可以通过map中getOrDefault方法设置它的第一次出现
//map.put(word, map.getOrDefault(word,0)+1);
//方法2，通过if-else，当出现为空时，那就更新value值；不为空时就加1
if (map.get(word) == null){//如果这个单词在之前遍历时没有出现过，那就
map.put(word, 1);
}else{
map.put(word, map.get(word)+1);
}
}
//建立小根堆
PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
//当字母频率相同时，按照字母建立大根堆
if (o1.getValue().compareTo(o2.getValue()) == 0){
return o2.getKey().compareTo(o1.getKey());
}
return o1.getValue() - o2.getValue();
}
});
//遍历map，调整优先级队列
for(Map.Entry<String, Integer> entry : map.entrySet()){
if (minHeap.size() < k){
minHeap.offer(entry);
}
else{
Map.Entry<String, Integer> top = minHeap.peek();
//频率相同时，也就是出现次数相同时
if (top.getValue().compareTo(entry.getValue()) == 0){
//字母小的先进来
if(top.getKey().compareTo(entry.getKey()) > 0){
//top的单词比进来的要大，所以top要出队,entry要进队
minHeap.poll();
minHeap.offer(entry);
}
}else{
//
if(top.getValue().compareTo(entry.getValue())<0){
minHeap.poll();
minHeap.offer(entry);
}
}
}
}
List<String> ret = new ArrayList<>();
for (int i = 0; i < k; i++){
Map.Entry<String, Integer> top = minHeap.poll();
ret.add(top.getKey());
}
Collections.reverse(ret);
return ret;
}
