Top K Frequent Words(692)

Hash - Medium

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.
collections()、items()の使用
Runtime : 52 ms/Memory : 14.5 MB

from collections import Counter

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        answer = []
        freq = collections.Counter(words).most_common()
        # freq -> 빈도순으로 word 정렬
        dic = {} # 빈도가 같은 word들을 묶을 dictionary
        c = 0 # k개의 최다 빈도 word를 채우면 break를 걸기 위한 카운팅
        
        for i in range(len(freq)): # 빈도 같은 word끼리 묶기
            if freq[i][1] not in dic:
                dic[freq[i][1]] = [freq[i][0]]
            else:
                dic[freq[i][1]].append(freq[i][0])
                
        dic = list(dic.items()) 
        # (빈도, 빈도 같은 word 배열) 형태로 배열 만들기
        
        for i in range(len(dic)):
            dic[i] = list(dic[i]) # 튜플 -> 배열 전환
            dic[i][1] = sorted(dic[i][1]) # word 오름차순 정렬
            for j in range(len(dic[i][1])):
                if c == k: # 목표한 k개 채웠으면 끊기
                    break
                answer.append(dic[i][1][j])
                c += 1
                
        return answer

お尻を最大限に活用するソリューション