【Java数据结构】前K个高频单词

前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值；不为空时就加1if (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>>() {@Overridepublic 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>>() {@Overridepublic 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值；不为空时就加1if (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>>() {@Overridepublic 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;}