Top K Frequent Words - LeetCode
Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.
Example 1: Input: words = [“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: words = [“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] <= 10
words[i] consists of lowercase English letters.
k is in the range [1, The number of unique words[i]]
- code
class Solution {
public List<String> topKFrequent(String[] words, int k) {
HashMap<String, Integer> freq = new HashMap<>();
for (String word: words){
freq.put(word, freq.getOrDefault(word, 0) + 1);
}
// min heap, pop out the least frequency or the bigger lexi word
PriorityQueue<String> q = new PriorityQueue<>( (a, b) ->
freq.get(a) == freq.get(b) ? b.compareTo(a) : freq.get(a) - freq.get(b)
);
for (String word: freq.keySet()){
q.offer(word);
if (q.size() > k){
q.poll();
}
}
String[] res = new String[k];
for (int i = k-1; i >= 0; --i){
res[i] = q.poll();
}
return Arrays.asList(res);
}
}