692. Top K Frequent Words

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:

• 1 <= words.length <= 500
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• k is in the range [1, The number of unique words[i]]

Code

347. Top K Frequent Elements

class Solution {
    class Trie {
        class TrieNode {
            TrieNode[] children;
            boolean isWord;
            String word;

            public TrieNode(){
                children = new TrieNode[26];
                isWord = false;
                word = "";
            }
        }

        private TrieNode root;
        public Trie() {
            root = new TrieNode();

        }

        public void insert(String word) {
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++){
                int index = word.charAt(i) - 'a';
                if(node.children[index] == null){
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.isWord = true;
            node.word = word;
        }

        public List<String> getWords() {
            TrieNode node = root;
            List<String> res = new ArrayList<>();
            helper(res, node);
            return res;
        }

        private void helper(List<String> res, TrieNode root) {
            if(root == null) return;
            if(root.isWord) {
                res.add(root.word);
            }

            for(int i = 0; i < 26; i++) {
                if(root.children[i] != null) {
                    helper(res, root.children[i]);
                }
            }
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();

        for(String word:words){
            map.put(word, map.getOrDefault(word, 0)+1);
        }
        
        Trie[] buckets = new Trie[words.length];
        for(Map.Entry<String, Integer> entry : map.entrySet()){
            String word = entry.getKey();
            int freq = entry.getValue();

            if(buckets[freq] == null){
                buckets[freq] = new Trie();
            }

            buckets[freq].insert(word);
        }
        
        List<String> res = new LinkedList<>();

        for(int i = buckets.length - 1; i >= 0; i--) {
            if(buckets[i] != null) {
                for(String word : buckets[i].getWords()) {
                    if(res.size() == k) return res;
                    res.add(word);
                }
            }
        }

        return res;
    }
}

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<Map.Entry<String, Integer>> queue = new PriorityQueue<>((a, b) -> {
            int freqA = a.getValue();
            int freqB = b.getValue();
            if (freqA != freqB) {
                return freqA - freqB;
            } else {
                return b.getKey().compareTo(a.getKey());
            }
        });


        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            queue.offer(entry);

            if(queue.size() > k) queue.poll();
        }

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

        return res;
    }
}