【算法刷题】堆-前 k 个高频单词

梦里梦外; 2023-09-30 22:33 20阅读 0赞

## 3. 前 k 个高频单词 ##

[692. 前K个高频单词][692. _K]

给定一个单词列表 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] 的数量]

题解一：最大堆 + 哈希表

import heapq
    from collections import Counter
    
    class Solution:
        def topKFrequent(self, words: List[str], k: int) -> List[str]:
            info = Counter(words)
            max_heap = []
            for word, cnt in info.items():
                heapq.heappush(max_heap, (-cnt, word))
            
            r = []
            while k:
                temp = heapq.heappop(max_heap)
                r.append(temp[1])
                k -= 1
    
            return r

*  `Counter` 会获取元素的个数，并按照从大到小排序
 *  `heapq.heappush([], item)`：可以添加元组，按照第一个元素进行排序，若第一个元素也相同，则按照字典序排序

def demo1():
        words = [(2, 'b'), (2, 'a'), (3, 'b'), (1, 'c')]
        min_heap = []
        for word in words:
            heapq.heappush(min_heap, word)
    
        while len(min_heap):
            print(heapq.heappop(min_heap))
        
        """
        (1, 'c')
        (2, 'a')
        (2, 'b')
        (3, 'b')
        """

--------------------

题解二：`cmp_to_key + sorted`

import heapq
    from functools import cmp_to_key
    
    class Solution:
        def topKFrequent(self, words: List[str], k: int) -> List[str]:
            # 哈希表保存 word 个数
            info = {
        }
            for word in words:
                info[word] = info.get(word, 0) + 1
    
            # 排序
            def compare(word1, word2):
                """比较相邻两个单词"""
                if info[word1] == info[word2]:  
                    # 单词数目相同，比较单词的字典序
                    if word1 < word2:
                        return -1
                    else:
                        return 1
    
                elif info[word1] > info[word2]: # 前一个单词的次数大于后一个单词次数，不交换
                    return -1
                else:
                    return 1    # 小于则交换
    
            return sorted(info.keys(), key=cmp_to_key(compare))[:k]

> 注意：`sorted` 的 `key` 参数提供的比较函数，默认只能提供一个元素，如果想两两比较，提供两个元素可以使用 `cmp_to_key` 方法。

> 参考：[692.前K个高频单词 Python双解，包教包会！][692._K_ Python]

[692. _K]: https://leetcode.cn/problems/top-k-frequent-words/
[692._K_ Python]: https://leetcode.cn/problems/top-k-frequent-words/solution/692qian-kge-gao-pin-dan-ci-pythonshuang-eqc94/