692. Top K Frequent Words

https://leetcode.com/problems/top-k-frequent-words/

solution

• hash

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        freq_dict = {}
        for word in words:
            if word not in freq_dict:
                freq_dict[word] = 0
            freq_dict[word] += 1

        freq_dict = sorted(freq_dict.items(), key=lambda x: (-x[1], x[0]), reverse=False)
        return [i[0] for i in freq_dict[:k]]

时间复杂度：O() 空间复杂度：O()

• heap

# 注意为了更好的控制频率相同的按字典排序, 需要增加一个类: https://walkccc.me/LeetCode/problems/0692/#__tabbed_2_3

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        mydict = {}
        for word in words:
            mydict[word] = mydict.get(word, 0) + 1

        heap = []
        for key, freq in mydict.items():
            heapq.heappush(heap, (-freq, key))

        res = []
        for _ in range(k):
            res.append(heapq.heappop(heap)[1])
        return res

时间复杂度：O() 空间复杂度：O()

• Bucket Sort