692. Top K Frequent Words

Posted on | Edited on | Views:

LeetCode

Approach #1: Sorting [Accepted], Time Complexity: O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> count = new HashMap();
        for (String word: words) {
            count.put(word, count.getOrDefault(word, 0) + 1);
        }
        List<String> candidates = new ArrayList(count.keySet());
        Collections.sort(candidates, (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
                w1.compareTo(w2) : count.get(w2) - count.get(w1));

        return candidates.subList(0, k);

Approach #2: Heap [Accepted], Time Complexity: O(Nlogk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> count=new HashMap<>();
        for(String word:words) count.put(word, count.getOrDefault(word,0)+1);
        
        PriorityQueue<String> heap=new PriorityQueue<String>(
        (w1,w2)->count.get(w1).equals(count.get(w2))?w2.compareTo(w1):count.get(w1)-count.get(w2)
        );
        
        for(String word:count.keySet()){
            heap.offer(word);
            if(heap.size()>k) heap.poll();
        }
        
        List<String> ans=new ArrayList<>();
        while(!heap.isEmpty()) ans.add(heap.poll());
        Collections.reverse(ans);
        return ans;
    }
}

0%