Top K Frequent Words 471

Question

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

Example:

[ "yes", "lint", "code",

"yes", "code", "baby",

"you", "baby", "chrome",

"safari", "lint", "code",

"body", "lint", "code" ]

当k=3时，返回["code", "lint", "baby"]

当k=4时，返回["code", "lint", "baby", "yes"]

Note

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.

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.

Tags Expand

Hash Table Heap Priority Queue

Discussion

1) 统计每个单词出现次数

2) 用最大堆来找到次数最大的单词

3) 用最小堆来确定相同次数时单词的顺序

Solution

1) HashMap + PriorityQueue(MinHeap)

遍历数组来统计词频。用一个Node class来表示每个单词和其词频。用一个HashMap来存每个单词和其node。用一个PriorityQueue来对HashMap中的node进行排序，重构Comparator来实现1)按词频重大到小排序2)词频相同时，按字典序排序。然后依次取k个queue顶元素。

2) Trie + MinHeap

学完Trietree再来补上

代码如下：

HashMap + PriorityQueue:

public class Solution {
    class Node{
        int frequence;
        String str;
        public Node(String s, int f){
            frequence = f;
            str = s;
        }
    }

    public String[] topKFrequentWords(String[] string, int k){

        if(string == null || string.length == 0 || k <= 0){
            return null;
        }

        HashMap<String, Node> map = new HashMap<String, Node>();
        for(String curt : string){
            if(!map.containsKey(curt)){
                map.put(curt, new Node(curt, 1));
            }
            map.get(curt).frequence = map.get(curt).frequence + 1;
        }

        PriorityQueue<Node> queue = new PriorityQueue<Node>(k, new Comparator<Node>(){
            public int compare(Node n1, Node n2){
                if(n1.frequence == n2.frequence){
                    return n1.str.compareTo(n2.str);
                }else{
                    return n2.frequence - n1.frequence;
                }
            }
        });

        for(String key : map.keySet()){
            queue.offer(map.get(key));
        }

        String[] result = new String[k];
        for(int i = 0; i < k; i++){
            result[i] = queue.poll().str;
        }

        return result;
    }
}

Trie + MinHeap: