用react做的网站上传,wordpress适合做企业站,中国广告设计网站,微信代运营加盟1、优先队列好像一般都叫堆#xff0c;以大顶堆为例#xff0c;顶部第一个元素最大#xff0c;底部最后一个元素最小#xff0c;自顶向底是递减的#xff08;更准确的说是非递增的#xff09;#xff0c;对外只能访问顶部第一个元素#xff08;对应索引为0#xff09;… 1、优先队列好像一般都叫堆以大顶堆为例顶部第一个元素最大底部最后一个元素最小自顶向底是递减的更准确的说是非递增的对外只能访问顶部第一个元素对应索引为0和底部最后一个元素对应索引为-1在Python中heapq默认维护小顶堆构造大顶堆时需要在入堆时添加相反数 2、本次博客总结下用优先队列解决TopK简单问题比如数组中第K大或小的元素、单个序列里第K大或小的距离、根据元素的出现频率排序的问题 215. 数组中的第K个最大元素 1、TopK简单问题的经典题目求第K大直接想到用大顶堆把数组中所有元素入堆返回堆中第k个元素作为结果 2、该题也可以用小顶堆始终维护堆的元素总数为k那么堆顶元素即为第k个最大元素——这种解法在实际中更合适好像有一种TopK 大用小顶堆TopK 小用大顶堆反着来的意思 from typing import List
import heapq215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:输入: [3,2,1,5,6,4], k 2输出: 5
题眼Top K
思路1、大顶堆返回堆中第k个元素作为结果
思路2、小顶堆始终维护堆的元素总数为k那么堆顶元素即为第k个最大元素
class Solution:def findKthLargest(self, nums: List[int], k: int) - int:# # 思路1、大顶堆返回堆中第k个元素作为结果# que []# for n in nums:# heapq.heappush(que, -n) # 添加相反数因为python默认维护小顶堆# for _ in range(k - 1):# heapq.heappop(que)# return -que[0]# 思路2、小顶堆始终维护堆的元素总数为k那么堆顶元素即为第k个最大元素que []for n in nums:heapq.heappush(que, n)if len(que) k:heapq.heappop(que)return que[0]if __name__ __main__:obj Solution()while True:try:in_line input().strip().split()nums []for n in in_line[0].split([)[1].split(])[0].split(,):nums.append(int(n))k int(in_line[1].strip())print(obj.findKthLargest(nums, k))except EOFError:break414. 第三大的数 1、TopK简单问题的经典题目是“215. 数组中的第K个最大元素”的特例K取3同时注意这个题有两个细节一是要把元素去重使用集合二是去重后元素总数不足3个时返回最大值 2、按照上一个题的经验TopK 大用小顶堆TopK 小用大顶堆反着来这道题直接用小顶堆并始终维护堆的元素总数不超过k from typing import List
import heapq414. 第三大的数
给你一个非空数组返回此数组中 第三大的数 。如果不存在则返回数组中最大的数。
示例 1:输入[2, 2, 3, 1]输出1解释注意要求返回第三大的数是指在所有不同数字中排第三大的数。此例中存在两个值为 2 的数它们都排第二。在所有不同数字中排第三大的数为 1 。
题眼Top K
思路“215. 数组中的第K个最大元素”的扩展需要先将元素去重复
class Solution:def thirdMax(self, nums: List[int]) - int:nums set(nums) # 去重# 小顶堆维持元素总数为3que []for n in nums:heapq.heappush(que, n)if len(que) 3:heapq.heappop(que)if len(que) 3:return que[-1]else:return que[0]if __name__ __main__:obj Solution()while True:try:in_line input().strip()[1: -1]nums [int(i) for i in in_line.split(,)]print(obj.thirdMax(nums))except EOFError:break703. 数据流中的第 K 大元素 1、TopK简单问题的经典题目是“215. 数组中的第K个最大元素”的扩展数组会不断的添加新元素进来并要求添加元素时返回此时新数组的第 K 大元素 2、按照“215. 数组中的第K个最大元素”的经验TopK 大用小顶堆TopK 小用大顶堆反着来这道题直接用小顶堆并始终维护堆的元素总数不超过K这样添加新元素时进行一次入堆和一次出堆就搞定了用大顶堆就会比较麻烦了 from typing import List
import heapq703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。
请实现 KthLargest 类
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后返回当前数据流中第 k 大的元素。
示例 1:输入[KthLargest, add, add, add, add, add][[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]输出[null, 4, 5, 5, 8, 8]解释KthLargest kthLargest new KthLargest(3, [4, 5, 8, 2]);kthLargest.add(3); // return 4kthLargest.add(5); // return 5kthLargest.add(10); // return 5kthLargest.add(9); // return 8kthLargest.add(4); // return 8
题眼Top K“215. 数组中的第K个最大元素”的扩展
思路、小顶堆始终维护堆的元素总数为k那么堆顶元素即为第k个频率的元素
class KthLargest:def __init__(self, k: int, nums: List[int]):self.que []self.k k# 建立小顶堆维护并保持总的元素数量为k那么堆顶即为第k个最大的数for n in nums:heapq.heappush(self.que, n)if len(self.que) k:heapq.heappop(self.que)def add(self, val: int) - int:heapq.heappush(self.que, val) # 为了防止队列内元素总数不足k个因此把元素先加进去if len(self.que) self.k:heapq.heappop(self.que)return self.que[0]if __name__ __main__:obj KthLargest(3, [4, 5, 8, 2])print(obj.add(3))print(obj.add(5))print(obj.add(10))print(obj.add(9))print(obj.add(4))973. 最接近原点的 K 个点 1、TopK简单问题的经典题目是“215. 数组中的第K个最大元素”的扩展只要简单计算下距离就转换为第K小元素了 2、按照“215. 数组中的第K个最大元素”的经验TopK 大用小顶堆TopK 小用大顶堆反着来这道题直接用大顶堆并始终维护堆的元素总数不超过K注意用小顶堆在Python中是添加相反数 from typing import List
import heapq973. 最接近原点的 K 个点
给定一个数组 points 其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点并且是一个整数 k 返回离原点 (0,0) 最近的 k 个点。
这里平面上两点之间的距离是 欧几里德距离 √(x1 - x2)2 (y1 - y2)2 。
你可以按 任何顺序 返回答案。除了点坐标的顺序之外答案 确保 是 唯一 的。
示例 1:输入points [[1,3],[-2,2]], k 1输出[[-2,2]]解释 (1, 3) 和原点之间的距离为 sqrt(10)(-2, 2) 和原点之间的距离为 sqrt(8)由于 sqrt(8) sqrt(10)(-2, 2) 离原点更近。我们只需要距离原点最近的 K 1 个点所以答案就是 [[-2,2]]。
题眼Top K“215. 数组中的第K个最大元素”的扩展
思路、题目是要求k个最小值大顶堆始终维护堆的元素总数为k那么堆内元素即为k个最小值
class Solution:def kClosest(self, points: List[List[int]], k: int) - List[List[int]]:# k个最小值大顶堆维持元素总数为kresult []que []for point in points:x, y point[0], point[1]d x * x y * yheapq.heappush(que, (-d, [x, y])) # 添加相反数因为python默认维护小顶堆if len(que) k:heapq.heappop(que)for _ in range(k):result.append(heapq.heappop(que)[1])return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()points []for row in in_line[1][2: -5].split(])[: -1]:points.append([int(n) for n in row.split([)[1].split(,)])k int(in_line[2].strip())print(obj.kClosest(points, k))except EOFError:break347. 前 K 个高频元素 1、TopK简单问题的经典题目是“215. 数组中的第K个最大元素”的扩展需要先统计元素出现频率的哈希表然后就是Top K问题的模板了 2、按照“215. 数组中的第K个最大元素”的经验TopK 大用小顶堆TopK 小用大顶堆反着来这道题直接用小顶堆并始终维护堆的元素总数不超过K注意入堆的形式为频率元素的元组 from typing import List
import heapq347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:输入: nums [1,1,1,2,2,3], k 2输出: [1,2]
题眼Top K“215. 数组中的第K个最大元素”的扩展
思路1、大顶堆返回堆中第k个频率的元素作为结果
思路2、小顶堆始终维护堆的元素总数为k那么堆顶元素即为第k个频率的元素
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:# # 思路一、大顶堆返回堆中第k个频率的元素作为结果# # 1、统计数组元素频率# hashTable {}# for n in nums:# if n not in hashTable:# hashTable[n] 1# else:# hashTable[n] 1# # 2、构建大顶堆# que []# for key in hashTable:# heapq.heappush(que, (-hashTable[key], key)) # 添加相反数因为python默认维护小顶堆# # 3、输出大顶堆的前k个元素# result []# for i in range(k):# result.append(heapq.heappop(que)[1])# return result# # 思路二、小顶堆始终维护堆的元素总数为k那么堆顶元素即为第k个频率的元素# 1、统计数组元素频率hashTable {}for n in nums:if n not in hashTable:hashTable[n] 1else:hashTable[n] 1# 2、构建小顶堆并维持其元素数量不多于kque []for key in hashTable:heapq.heappush(que, (hashTable[key], key))if len(que) k:heapq.heappop(que)# 3、输出大顶堆的k个元素逆序放入结果数组result [0] * kfor i in range(k - 1, -1, -1):result[i] heapq.heappop(que)[1]return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()nums [int(i) for i in in_line[1].split([)[1].split(])[0].split(,)]k int(in_line[2].strip())print(obj.topKFrequent(nums, k))except EOFError:break451. 根据字符出现频率排序 1、TopK简单问题的经典题目是“215. 数组中的第K个最大元素”的扩展同样需要先统计元素出现频率的哈希表 2、这道题是要对所有的字符出现频率进行排序因此和“215. 数组中的第K个最大元素”的经验TopK 大用小顶堆TopK 小用大顶堆不那么一致了直接用大顶堆将所有频率元素的元组入堆然后持续出堆返回结果就可以了 import heapq451. 根据字符出现频率排序
给定一个字符串 s 根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串。如果有多个答案返回其中任何一个。
示例 1:输入: s tree输出: eert解释: e出现两次r和t都只出现一次。因此e必须出现在r和t之前。此外eetr也是一个有效的答案。
题眼Top K
思路这道题是要对所有的字符出现频率进行排序因此和“215. 数组中的第K个最大元素”的经验TopK 大用小顶堆TopK 小用大顶堆不那么一致了直接用大顶堆
将所有频率元素的元组入堆然后持续出堆返回结果就可以了
class Solution:def frequencySort(self, s: str) - str:# 1、统计词频hashTable {}for ch in s:if ch not in hashTable:hashTable[ch] 1else:hashTable[ch] 1# 2、建立大顶堆que []for k in hashTable:heapq.heappush(que, (-hashTable[k], k))# 3、建立结果字符串result while len(que) 0:pair heapq.heappop(que)result pair[1] * (-pair[0])return resultif __name__ __main__:obj Solution()while True:try:s input().strip().split()[1].strip()[1: -1]print(obj.frequencySort(s))except EOFError:break692. 前K个高频单词 1、TopK简单问题的经典题目是“215. 数组中的第K个最大元素”的扩展同样需要先统计元素出现频率的哈希表额外增加了对词频相同的元素的排序要求字典次序小的排前面因此需要重写即__lt__()函数 2、按照“215. 数组中的第K个最大元素”的经验TopK 大用小顶堆TopK 小用大顶堆反着来这道题直接用小顶堆并始终维护堆的元素总数不超过K注意入堆的形式为频率元素的元组 3、由于维护的是小顶堆那么频率值小的就要排在堆顶频率值一样时让字典次序大的排在堆顶这样保留下来的K个元素就满足题意要求的频率值大字典次序小最后把这些元素出堆逆序存放到结果数组中 from typing import List
import heapq692. 前K个高频单词
给定一个单词列表 words 和一个整数 k 返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率 按字典顺序 排序。
示例 1:输入: words [i, love, leetcode, i, love, coding], k 2输出: [i, love]解析: i 和 love 为出现次数最多的两个单词均为2次。注意按字母顺序 i 在 love 之前。
题眼Top K“215. 数组中的第K个最大元素”的扩展
思路题目是要求k个最大值小顶堆始终维护堆的元素总数为k那么堆内元素即为k个最大值
难点这道题对答案的唯一性进行了限制因此要重写小于号
class Solution:def topKFrequent(self, words: List[str], k: int) - List[str]:class Comparer: # 重写小于号出现次数少的在堆顶、次数一样字典序大的在堆顶def __init__(self, val, key):self.val valself.key keydef __lt__(self, other):if self.val ! other.val:return self.val other.valreturn self.key other.key# 1、统计词频hashTable {}for n in words:if n not in hashTable:hashTable[n] 1else:hashTable[n] 1# 2、建立优先队列维护元素总数为kque []for key in hashTable:heapq.heappush(que, Comparer(hashTable[key], key))if len(que) k:heapq.heappop(que)# 3、输出结果result [0] * kfor i in range(k - 1, -1, -1):result[i] heapq.heappop(que).keyreturn result
