前K个高频单词

难度: Medium

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

注意：

1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]

进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

Submission

运行时间: 24 ms

内存: 16.1 MB

class Word:
    def __init__(self, times, word):
        self.times = times
        self.word = word

    def __lt__(self, other):
        if self.times != other.times:
            return self.times < other.times
        return self.word > other.word


class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        """
        topK 问题，堆
        """
        m = defaultdict(int)
        heap = []
        for word in words:
            m[word] += 1
        for word, times in m.items():
            heapq.heappush(heap, Word(times, word))
            while len(heap) > k:
                heapq.heappop(heap)
        ret = []
        while heap:
            ret.append(heapq.heappop(heap).word)
        ret.reverse()
        return ret

Explain

此题解采用哈希表和最小堆（优先队列）的结合来解决问题。首先，使用一个哈希表（defaultdict）统计每个单词的出现次数。然后，定义一个自定义对象Word，它包含单词出现的次数和单词本身，重载其比较运算符以实现优先队列的正确功能。在遍历哈希表时，将每个单词以Word对象的形式添加到一个最小堆中。如果堆的大小超过k，则移除堆顶元素（出现次数最少的元素），以保持堆的大小为k。最后，从堆中取出所有元素，这些元素是按出现频率最小到最大排序的，所以需要反转以得到正确的顺序。

时间复杂度: O(n log k)

空间复杂度: O(n)

class Word:
    def __init__(self, times, word):
        # 初始化单词及其出现次数
        self.times = times
        self.word = word

    def __lt__(self, other):
        # 定义比较规则：先按次数比较，次数相同再按字典顺序
        if self.times != other.times:
            return self.times < other.times
        return self.word > other.word


class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        # 使用哈希表统计每个单词的频率
        m = defaultdict(int)
        heap = []
        for word in words:
            m[word] += 1
        # 使用最小堆维护前k个高频单词
        for word, times in m.items():
            heapq.heappush(heap, Word(times, word))
            # 保证堆的大小不超过k
            while len(heap) > k:
                heapq.heappop(heap)
        ret = []
        # 从堆中取出所有元素并反转以获得正确顺序
        while heap:
            ret.append(heapq.heappop(heap).word)
        ret.reverse()
        return ret

Explore

使用最小堆来维护前k个高频单词的主要原因是效率和简便性。最小堆使得我们能够快速移除堆中频率最低的单词（即堆顶元素），这样可以确保堆中始终保持最高的k个频率的单词。如果使用最大堆，则每次插入新元素后都需要检查整个堆以确定哪些元素需要被移除，这会增加算法的复杂度。而使用最小堆，只需要比较和可能移除顶部元素即可简单维护堆的大小为k，从而保证时间复杂度较低。其他数据结构如排序数组或列表虽然可以维持元素的顺序，但更新元素的成本较高，特别是在频繁插入和删除操作时效率较低。

在Word类中重载比较运算符`__lt__`时，定义了两个主要的比较准则：首先比较单词出现的次数，如果次数相同，则按照字典顺序比较单词本身。具体实现是这样的：如果两个Word对象的`times`（出现次数）不同，则根据次数进行比较，次数少的对象视为较小。如果`times`相同，则比较两个单词的字典顺序，但由于我们需要字典顺序靠前的单词在堆中表现为较小（即更晚被移除），因此在次数相同的情况下，字典顺序靠后的单词应该返回True表示它比较小。这样可以确保在频率相同的情况下，字典顺序靠前的单词在优先队列中优先级更高。

由于使用的是最小堆，堆顶元素始终是频率最小的元素，当我们对堆元素进行pop操作时，它们是按频率从小到大的顺序被移除的。但是题目要求输出的是按频率从大到小的顺序。因此，为了获得正确的顺序，我们需要在取出所有元素后将结果列表进行反转。如果尝试在插入时就维持一个从大到小的顺序，我们需要使用最大堆，并且还要管理堆的大小限制为k，这在逻辑上更复杂且易出错。使用最小堆并在最后进行反转是一个更简单且效率高的处理方式。