*692. Top K Frequent Words

解法一 Override Collections.sort()

思路

We can use a HashMap to count the frequnecy of each word, and then add then into a list.
When sorting the list, override the sorting rules according to requirements. We sort the list by descending order, and if two Strings has equal frequency, the lower alphabetical order comes first.
After sorting, we take a sublist of the sorted list.

代码

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> res = new ArrayList<>();
        if (words.length == 0 || words == null) return res;

        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        Set<Map.Entry<String, Integer>> set = map.entrySet();

        for (Map.Entry<String, Integer> s : set) {
            res.add(s.getKey());
        }

        Collections.sort(res, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                if (map.get(a) == map.get(b)) {
                    return a.compareTo(b);
                }
                return map.get(b) - map.get(a);
            }
        });

        return res.subList(0, k);
    }
}

复杂度分析

时间复杂度
Counting the frequence for each word costs O(n), adding the word to list costs O(n), and sort the list costs O(nlogn).
空间复杂度
O(n) because we use a HashMap to count the frequency.

解法二

思路

Use the HashMap to count frequency for each word. Initialize a priority queue to sort the top k words. Override the rules for sorting - Worst frequent word at the top, if frequency is the same, the word with higher alphabetical comes first. So we can always poll the first element to keep the pq with size k.
Use a LinekdList to store the result. Always add the polled top element to the head of LinkedList.

代码

class Solution {
    public List<String> topKFrequent (String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> map.get(a).equals(map.get(b)) ? b.compareTo(a) : map.get(a) - map.get(b));

        for (String word : map.keySet()) {
            pq.offer(word);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        List<String> res = new LinkedList<>();
        while(!pq.isEmpty()) {
            res.add(0, pq.poll());
        }

        return res;
    }
}

复杂度分析

时间复杂度
O(nlogk), because when add elements to pq, it takes O(logk) and we add words n times.
空间复杂度
O(n)

Takeaway

• 重新复习了 Override Comparator 的几种方法， 对于 PriorityQueue, override 其中的排序规则；对于 List, Override Collections.sort() 的排序规则。
• List<Stirng> list = new LinkedList 时，由于多态，LinkedList 继承 List 全部方法，而没有专属 LinkedList 的方法。所以使用 list.add(0, element) 来将元素添加进头部。
• 两个方法都对 sorting 规则进行了重写，但是第一种方法使用递减因为我们之间截取 list 即可，第二种方法使用递增因为 PriorityQueue 的性质，我们每次都对头部元素删除保证 pq 的 size 为 k，势必只能删除 least frequent element。 为保证结果为正常顺序，每次将 poll() 的元素加入 list 头部即可。
• list.subList(0, k) -- 截取 list 的 [0, k) 元素形成新的 list。

本作品采用《CC 协议》，转载必须注明作者和本文链接