算法刷题之堆

爱被打了一巴掌 2023-09-30 21:27 1阅读 0赞

## 1. heapq 堆 ##

`Python` 中只有最小堆：

import heapq
    
    a = []
    heapq.heappush(a, 3)  # 添加元素
    heapq.heappush(a, 2)
    heapq.heappush(a, 1)
    while len(a):  # 判断堆的长度
        print(heapq.heappop(a))  # 弹出堆顶元素
    
    # 将列表转换为最小堆
    nums = [2, 3, 1, 4, 5, 6]
    heapq.heapify(nums)
    while len(nums):
        print(heapq.heappop(nums))
    
    # 转换为最大堆
    nums_1 = [2, 3, 1, 4, 5, 6]
    max_heap = []
    for i in max_heap:
        heapq.heappush(max_heap, i * -1)  # 对当前元素乘 -1 ，取出来后再乘以 -1

## 2. 数组中的第 K 个最大元素 ##

[215. 数组中的第K个最大元素][215. _K]

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    
    请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    
    示例 1:
    
    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5
    示例 2:
    
    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4
     
    提示：
    
    1 <= k <= nums.length <= 104
    -104 <= nums[i] <= 104

题解一：最小堆变成最大堆

import heapq
    
    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            # 最小堆变为最大堆
            a = list(map(lambda x: x * -1, nums))
            heapq.heapify(a)
            
            r = ""
            while k:
                r = heapq.heappop(a) * -1
                k -= 1
    
            return r

题解二：

import heapq
    
    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            nums.sort()
    
            return nums[-k]

## 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]

[215. _K]: https://leetcode.cn/problems/kth-largest-element-in-an-array/
[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/