leetcode分类刷题：队列（Queue）（二、优先队列解决TopK简单问题）

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 heapq
'''
215. 数组中的第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:break

414. 第三大的数

1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的特例，K取3，同时注意这个题有两个细节：一是要把元素去重（使用集合），二是去重后元素总数不足3个时，返回最大值
2、按照上一个题的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过k

from typing import List
import heapq
'''
414. 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 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:break

703. 数据流中的第 K 大元素

1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，数组会不断的添加新元素进来，并要求添加元素时返回此时新数组的第 K 大元素
2、按照“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过K，这样添加新元素时，进行一次入堆和一次出堆就搞定了，用大顶堆就会比较麻烦了

from typing import List
import heapq
'''
703. 数据流中的第 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 heapq
'''
973. 最接近原点的 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:break

347. 前 K 个高频元素

1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，需要先统计元素出现频率的哈希表，然后就是Top K问题的模板了
2、按照“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过K，注意入堆的形式为（频率，元素）的元组

from typing import List
import heapq
'''
347. 前 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:break

451. 根据字符出现频率排序

1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，同样需要先统计元素出现频率的哈希表，
2、这道题是要对所有的字符出现频率进行排序，因此和“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆不那么一致了，直接用大顶堆，将所有（频率，元素）的元组入堆，然后持续出堆返回结果就可以了

import heapq
'''
451. 根据字符出现频率排序
给定一个字符串 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:break

692. 前K个高频单词

1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，同样需要先统计元素出现频率的哈希表，额外增加了对词频相同的元素的排序要求：字典次序小的排前面，因此需要重写<，即__lt__()函数
2、按照“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过K，注意入堆的形式为（频率，元素）的元组，
3、由于维护的是小顶堆，那么频率值小的就要排在堆顶，频率值一样时让字典次序大的排在堆顶，这样保留下来的K个元素就满足题意要求的频率值大，字典次序小，最后把这些元素出堆逆序存放到结果数组中

from typing import List
import heapq
'''
692. 前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