leetcode

题目链接

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

解题思路与代码思路：

哈希排序法

建立字典，把单词和频次对应记录下来，提取字典的items来排序，在快排的key中使用lambda，可以给频次添加负数就是倒序，然后再根据单词来排序

最小堆法

除了自己建立字典，也可以使用Counter直接获得一个字典，把字典的元素作为元组存到一个列表中，对列表建立最小堆，把k个最小堆顶的元素pop出。
还有一种简单写法，nsmallest

代码：

哈希排序法

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        count_dict = {}
        for i in words:
            if i not in count_dict:
                count_dict[i] = count_dict.get(i,0) + 1
            count_dict[i] += 1
            
        count_dict = sorted(count_dict.items(),key=lambda item:(-item[1],item[0]))
        return [count_dict[i][0] for i in range(k)]

最小堆法

count = collections.Counter(words)
heap = [(-freq,word) for word,freq in count.items()]
heapq.heapify(heap)
return [heapq.heappop(heap)[1] for _ in range(k)]

count = collections.Counter(words)
return heapq.nsmallest(k, count, lambda s: (-count[s], s))

$复杂度分析：$

1. 哈希排序法

• 时间复杂度：N是words列表长度，使用O(N)的时间计算每个单词的频率，然后用O(NlogN)排序单词，所以时间复杂度为O(NlogN)
• 空间复杂度：O(N)，字典存放

2. 最小堆法

• 时间复杂度：O(N)的时间计算频率，添加每个单词进入堆O(logK)，k小于等于N，时间复杂度是O(NlogK)
• 空间复杂度：O(N) ，堆的空间