LeetCode 솔루션 분류
[10/19] 692. Top K Frequent Words
본문
Medium
6373296Add to ListShareGiven 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].length <= 10
words[i]
consists of lowercase English letters.k
is in the range[1, The number of unique words[i]]
Follow-up: Could you solve it in O(n log(k))
time and O(n)
extra space?
Accepted
497,277
Submissions
875,082
태그
#Amazon, #Uber, #Google, #Yahoo, #Bloomberg, #Microsoft, #Facebook, #Apple, #Adobe, #Atlassian, #IBM
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
import heapq
import collections
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
counter = collections.Counter(words)
max_heap = []
for key, val in counter.items():
max_heap.append((-val, key))
heapq.heapify(max_heap)
res = []
while k and max_heap:
freq, word = heapq.heappop(max_heap)
res.append(word)
k -= 1
return res