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.
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.
Follow up:
Try to solve it in O[n log k] time and O[n] extra space.
class Solution:
def topKFrequent[self, words, k]:
"""
:type words: List[str]
:type k: int
:rtype: List[str]
"""
return [w for w, v in sorted[collections.Counter[words].items[], key = lambda x: [-x[1], x[0]]] [:k]]
class WordFreq:
def __init__[self, freq, word]:
self.freq = freq
self.word = word
def __lt__[self, other]:
if self.freq != other.freq:
# return self.freq.__lt__[other.freq]
return self.freq other.word
class Solution:
def topKFrequent[self, words, k]:
"""
:type words: List[str]
:type k: int
:rtype: List[str]
"""
counts = collections.Counter[words]
topk = []
heapq.heapify[topk]
for word, freq in counts.items[]:
heapq.heappush[topk, WordFreq[freq, word]]
# solution 2:
# heapq.heappush[topk, [WordFreq[freq, word], word]]
if len[topk] > k:
heapq.heappop[topk]
res = []
for _ in range[k]:
res.append[heapq.heappop[topk].word]
# solution 2:
# res.append[heapq.heappop[topk][1]]
return res[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| struct T {
string word;
int freq;
T[string word, int freq] : word[word], freq[freq] {}
};
class Solution {
public:
vector topKFrequent[vector& words, int k] {
vector ans;
unordered_map count;
// Words w/ higher frequency and lower alphabetical order are in the bottom
// Of the heap, because we'll pop words w/ lower frequency and higher
// Alphabetical order if the heap's size > k
auto compare = [][const T& a, const T& b] {
return a.freq == b.freq ? a.word b.freq;
};
priority_queue heap[compare];
for [const string& word : words]
++count[word];
for [const auto& [word, freq] : count] {
heap.emplace[word, freq];
if [heap.size[] > k]
heap.pop[];
}
while [!heap.empty[]]
ans.push_back[heap.top[].word], heap.pop[];
reverse[begin[ans], end[ans]];
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class T {
public String word;
public int freq;
public T[String word, int freq] {
this.word = word;
this.freq = freq;
}
};
class Solution {
public List topKFrequent[String[] words, int k] {
List ans = new ArrayList[];
Map count = new HashMap[];
// Words w/ higher frequency and lower alphabetical order are in the bottom
// Of the heap, because we'll pop words w/ lower frequency and higher
// Alphabetical order if the heap's size > k
Queue heap = new PriorityQueue[
[a, b] -> a.freq == b.freq ? b.word.compareTo[a.word] : a.freq - b.freq];
for [final String word : words]
count.put[word, count.getOrDefault[word, 0] + 1];
for [final String word : count.keySet[]] {
heap.offer[new T[word, count.get[word]]];
if [heap.size[] > k]
heap.poll[];
}
while [!heap.isEmpty[]]
ans.add[heap.poll[].word];
Collections.reverse[ans];
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class T:
def __init__[self, word: str, freq: int]:
self.word = word
self.freq = freq
def __lt__[self, other]:
if self.freq == other.freq:
# Words w/ higher frequency and lower alphabetical order are in the bottom
# Of the heap, because we'll pop words w/ lower frequency and higher
# Alphabetical order if the heap's size > k
return self.word > other.word
return self.freq List[str]:
ans = []
heap = [] # Sorted by freq then alphabet
for word, freq in Counter[words].items[]:
heapq.heappush[heap, T[word, freq]]
if len[heap] > k:
heapq.heappop[heap]
while heap:
ans.append[heapq.heappop[heap].word]
return ans[::-1]
|