# 692. Top K Frequent Words

## 1.Description(Medium)

Given a list of words and an integer k, return the top k frequent words in the list.

### Notice

You should order the words by the frequency of them in the return list, the most frequent one comes first. If two words has the same frequency, the one with lower alphabetical order come first.

**Example**

Given

```
[
    "yes", "lint", "code",
    "yes", "code", "baby",
    "you", "baby", "chrome",
    "safari", "lint", "code",
    "body", "lint", "code"
]
```

for k =`3`, return`["code", "lint", "baby"]`.

for k =`4`, return`["code", "lint", "baby", "yes"]`,

[**Challenge**](https://www.lintcode.com/en/problem/top-k-frequent-words/#challenge)

Do it in O(nlogk) time and O(n) extra space.

Extra points if you can do it in O(n) time with O(k) extra space approximation algorithms.

[**Tags**](https://www.lintcode.com/en/problem/top-k-frequent-words/#tags)

[Hash Table](https://www.lintcode.com/tag/hash-table/) [Heap](https://www.lintcode.com/tag/heap/) [Priority Queue](https://www.lintcode.com/tag/priority-queue/)

## 2.Code

**Version 1:  HashMap + PriorityQueue(MinHeap)**

遍历数组来统计词频。用一个Word class来表示每个单词和其词频。

用一个HashMap来存每个单词和其Word。

用一个PriorityQueue来对HashMap中Word进行排序，重构Comparator来实现

1\)按词频重大到小排序

2\)词频相同时，按字典序排序。(String.compareTo())

然后依次取k个queue顶元素。

注意一开始要判断k==0,否则在初始化priorityqueue的时候会报错。

```
class Word{
    String value;
    int freq;
    public Word(String value,int freq){
        this.value=value;
        this.freq=freq;
    }   
}

public class Solution_471 {
     /**
     * @param words an array of string
     * @param k an integer
     * @return an array of string
     */



    public String[] topKFrequentWords(String[] words, int k) {
        String[] result=new String[k];
        //一定注意这里要记得判断k==0,不然在定义priorityqueue的时候就会报错
        if(words==null || words.length==0 ||k==0){
            return result;
        }
        //min heap
        PriorityQueue<Word> queue=new PriorityQueue<Word>(k,new Comparator<Word>(){
            public int compare(Word a,Word b){
                int diff=a.freq-b.freq;
                if(diff==0){
                    //注意这里比较string的方法，相当于b-a,下面这个是错的
                    return b.value.compareTo(a.value);
                    //return b.value.charAt(0)-a.value.charAt(0);
                }
                return diff;
             }
        });

        HashMap<String,Word> map=new HashMap<String,Word>();//注意hashmap存放的是string和word的映射

        for(int i=0;i<words.length;i++){
            String current=words[i];
            if(!map.containsKey(current)){
                Word node=new Word(current,1);
                map.put(current, node);
            }else{
                Word update=map.get(current);
                update.freq++;
                map.put(current,update);
            }
        }
        for(String element:map.keySet()){
            Word node=map.get(element);
            queue.offer(node);
            if(queue.size()>k){
                queue.poll();
            }
        }

        int len=k-1;
        while(!queue.isEmpty()){
            result[len--]=queue.poll().value;
        }
        return result;
    }
}
```

**Version 2: Quick Select**

[**https://www.jiuzhang.com/problem/top-k-frequent-words/**](https://www.jiuzhang.com/problem/top-k-frequent-words/)<br>

最优解法：quick select

* Time: O(n + klogk)
* Space: O(n) HashMap
* HashMap 记录元素的频数

```
public class Solution {
    public String[] topKFrequentWords(String[] words, int k) {
        if (words == null || words.length == 0 || k == 0) {
            return new String[0];
        }
        
        // O(n) hashing
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
            counts.merge(word, 1, Integer::sum);
        }
        String[] wordSet = counts.keySet().toArray(new String[0]);
        
        // most frequent -> least frequent, then alphabetical order
        Comparator<String> comp = Comparator
            .comparing((String w) -> -counts.get(w)) 
            .thenComparing(Comparator.naturalOrder());
            
        // O(n) quick select
        quickSelect(wordSet, comp, 0, wordSet.length - 1, k - 1); 
        Arrays.sort(wordSet, 0, k - 1, comp);  // O(klogk) sort
        
        return Arrays.copyOf(wordSet, k); 
    }
    
    // Quick select with custom Comparator
    private String quickSelect(String[] words,  
                               Comparator<String> comp,
                               int start, 
                               int end, 
                               int k) {
        if (start >= end) {
            return words[k];
        }
        
        String pivot = words[start + (end - start) / 2];
        int left = start, right = end; 
        while (left <= right) {
            while (left <= right && comp.compare(words[left], pivot) < 0) {
                left++;
            }
            
            while (left <= right && comp.compare(words[right], pivot) > 0) {
                right--;
            }
            
            if (left <= right) {
                String temp = words[left];
                words[left++] = words[right];
                words[right--] = temp;
            }
        }
        
        if (k <= right) {
            return quickSelect(words, comp, start, right, k);
        }
        
        if (k >= left) {
            return quickSelect(words, comp, left, end, k);
        }
        
        return words[k];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/8.data-structure/top-k-frequent-words.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.