Algorithm
Problem Name: 692. Top K Frequent Words
Problem Link: https://leetcode.com/problems/top-k-frequent-words/
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 <= 5001 <= words[i].length <= 10words[i]consists of lowercase English letters.kis in the range[1, The number of unique words[i]]
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
vector<string>res;
unordered_map < string, int>m;
auto comp = [](pair<int, string>& a, pair<int, string>& b){ return a.first == b.first ? a.second < b.second : a.first > b.first; };
priority_queue < pair<int, string>, vector<pair<int, string> >, decltype(comp)>pq(comp);
for(auto x: words) m[x]++;
for(auto x: m){
pq.push({x.second, x.first});
if(pq.size() > k) pq.pop();
}
while(!pq.empty()) res.push_back(pq.top().second), pq.pop();
reverse(res.begin(), res.end());
return res;
}
};
Input
words = ["i","love","leetcode","i","love","coding"], k = 2
Output
["i","love"]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List topKFrequent(String[] words, int k) {
Map wordFrequency = new HashMap<>();
Map < Integer, Set();
int maxFrequency = 0;
for (String word : words) {
if (!wordFrequency.containsKey(word)) {
wordFrequency.put(word, 1);
frequencyToWord.computeIfAbsent(1, j -> new HashSet < >()).add(word);
} else {
int oldFrequency = wordFrequency.get(word);
int newFrequency = oldFrequency + 1;
wordFrequency.put(word, newFrequency);
frequencyToWord.get(oldFrequency).remove(word);
frequencyToWord.computeIfAbsent(newFrequency, j -> new HashSet < >()).add(word);
}
maxFrequency = Math.max(maxFrequency, wordFrequency.get(word));
}
List < String> result = new ArrayList<>();
for (int i = maxFrequency; i > 0 && result.size() < k; i--) {
List currFreqWords = new ArrayList<>(frequencyToWord.get(i));
Collections.sort(currFreqWords);
for (int j = 0; j < currFreqWords.size() && result.size() < k; j++) {
result.add(currFreqWords.get(j));
}
}
return result;
}
}
Input
words = ["i","love","leetcode","i","love","coding"], k = 2
Output
["i","love"]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const topKFrequent = function(words, k) {
const hash = {}
words.forEach(el => {
if(hash.hasOwnProperty(el)) {
hash[el]++
} else {
hash[el] = 1
}
})
const freqArr = new Array(words.length)
const keys = Object.keys(hash)
for(let k of keys) {
let freq = hash[k]
if(freqArr[freq] == null) {
freqArr[freq] = []
}
freqArr[freq].push(k)
}
const res = []
for(let i = freqArr.length; i >= 0 && res.length < k; i--) {
if(freqArr[i] != null) {
res.push(...(freqArr[i].sort()))
}
}
return res.slice(0, k>
};
Input
words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output
["the","is","sunny","day"]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def topKFrequent(self, words, k):
return [w for w, v in sorted(collections.Counter(words).items(), key = lambda x: (-x[1], x[0])) [:k]]
Input
words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output
["the","is","sunny","day"]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0692_TopKFrequentWords
{
public IList < string> TopKFrequent(string[] words, int k)
{
var counts = new Dictionary();
foreach (var word in words)
{
if (!counts.ContainsKey(word))
counts[word] = 1;
else
counts[word]++;
}
var heap = new SortedDictionary < (string word, int count), int>(Comparer<(string word, int count)>.Create((a, b) =>
{
var result = a.count.CompareTo(b.count);
if (result == 0)
result = -a.word.CompareTo(b.word);
return result;
}));
foreach (var word in counts.Keys)
{
heap[(word, counts[word])] = 1;
if (heap.Count > k)
heap.Remove(heap.Keys.First());
}
var results = new List < string>();
foreach ((string word, int count) in heap.Keys)
results.Add(word);
results.Reverse();
return results;
}
}
}
Input
words = ["i","love","leetcode","i","love","coding"], k = 2
Output
["i","love"]