堆

堆

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 个最大元素

给定整数数组 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 个高频单词

给定一个单词列表 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双解，包教包会！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。