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

2023-09-12 21:31:11

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)  # 去重
        # 小顶堆，维持元素总数为3
        que = []
        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 4
    kthLargest.add(5);   // return 5
    kthLargest.add(10);  // return 5
    kthLargest.add(9);   // return 8
    kthLargest.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个最小值，大顶堆：维持元素总数为k
        result = []
        que = []
        for point in points:
            x, y = point[0], point[1]
            d = x * x + y * y
            heapq.heappush(que, (-d, [x, y]))  # 添加相反数：因为python默认维护小顶堆
            if len(que) > k:
                heapq.heappop(que)
        for _ in range(k):
            result.append(heapq.heappop(que)[1])
        return result


if __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] = 1
            else:
                hashTable[n] += 1
        # 2、构建小顶堆，并维持其元素数量不多于k
        que = []
        for key in hashTable:
            heapq.heappush(que, (hashTable[key], key))
            if len(que) > k:
                heapq.heappop(que)
        # 3、输出大顶堆的k个元素，逆序放入结果数组
        result = [0] * k
        for i in range(k - 1, -1, -1):
            result[i] = heapq.heappop(que)[1]
        return result


if __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] = 1
            else:
                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 result


if __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 = val
                self.key = key

            def __lt__(self, other):
                if self.val != other.val:
                    return self.val < other.val
                return self.key > other.key

        # 1、统计词频
        hashTable = {}
        for n in words:
            if n not in hashTable:
                hashTable[n] = 1
            else:
                hashTable[n] += 1
        # 2、建立优先队列：维护元素总数为k
        que = []
        for key in hashTable:
            heapq.heappush(que, Comparer(hashTable[key], key))
            if len(que) > k:
                heapq.heappop(que)
        # 3、输出结果
        result = ['0'] * k
        for i in range(k - 1, -1, -1):
            result[i] = heapq.heappop(que).key
        return result
更多推荐

【大数据】HDFS 的常用命令

HDFS的常用命令1.操作命令1.1创建文件夹1.2列出指定的文件和目录1.3新建文件1.4上传文件1.5将本地文件移动到HDFS1.6下载文件1.7查看文件1.8追写文件1.9删除目录或者文件1.10显示占用的磁盘空间大小1.11HDFS中的文件复制1.12HDFS中的文件移动2.管理命令2.1报告文件系统的基本信息

ElasticSearch（二）

1.DSL查询文档elasticsearch的查询依然是基于JSON风格的DSL来实现的。1.1.DSL查询分类Elasticsearch提供了基于JSON的DSL（DomainSpecificLanguage）来定义查询。常见的查询类型包括：查询所有：查询出所有数据，一般测试用。例如：match_all全文检索（fu

高教杯数学建模A题程序设计要点与思路

2023年是我最后一次参加高教杯大学生数学建模竞赛以后不会再参加了（大四参加意义不太，研究生有研究生的数学建模大赛）很遗憾由于各种原因我们没有能够完成赛题2022年美赛2022年MathorCup2022年国赛2022亚太杯2023年美赛2023年国赛我和我的朋友一共参加了6次比赛6次比赛我交到了很好的朋友然鹅成绩比较

Java 8 新特性解读及应用实践

Java8新特性解读及应用实践一、简介二、Lambda表达式三、流式编程四、日期/时间API1.概述2.LocalDate、LocalTime、LocalDateTime等类的使用3.格式化与解析五、重复注解和类型注解1.概念与作用2.重复注解实例3.类型注解实例六、小结回顾一、简介Java8带来了众多重大改进和新特性

【网络协议】Http-上

Http请求结构：结构图1：实验解析请求报文：1.在Edge浏览器上输入ip地址+端口号+文件资源，也就是下图中的120.XX.139.29:8888/A/B/c.html2.我的程序接收到了一个没有有效载荷的http请求(呼应上面的结构图1)，如下GET/1/2/3.htmlHTTP/1.1//请求行（请求方法+请求

关于路由懒加载

路由懒加载是一种优化技术，它是可以延迟加载应用程序的某些模块或者组件，而不是在初始加载时一次性加载所有内容，这样可以减少初始加载的文件体积，提高应用程序的加载速度1.懒加载是在什么时候加载路由懒加载是在用户访问相应的路由时才进行加载。它延迟加载路由组件，使得在初始加载时只加载必要的代码，而将其他路由的代码推迟到需要时再

实验篇——根据群体经纬度提取环境数据（先导）

实验篇——根据群体经纬度提取环境数据（先导）文章目录前言一、获取数据文件1.1.经纬度文件1.2.环境数据的tif文件二、R语言代码实现三、环境文件介绍3.1.bio3.2.prec3.3.elev3.4.tmin3.5.tmax3.6.vapr13.7.tavg3.8.srad3.9.wind四、后续总结前言首先得到

LLM - 大模型技术报告与训练细节 By Baichuan2

目录一.引言二.Introduction-LLM相关进展1.模型参数越大，模型能力越强2.开源模型促进LLM领域快速发展3.开源模型集中在英文领域，其他语言能力有限4.训练数据2.6亿Token遥遥领先5.优化人类指令发布对应Chat模型6.公布了训练过程中的CKPT促进领域研究发展三.Pre-training-Bai

Vue路由与nodejs环境搭建

目录一、Vue路由1.1SPA简介1.2路由简介1.3路由实现思路1.3.1引入vue-router的js依赖1.3.2定义组件1.3.3定义路由1.3.4组装路由器1.3.5将路由挂载根实例1.3.6定义触发路由的按钮1.3.7定义锚点1.4示例二、nodejs环境搭建2.1nodejs简介2.2nodejs下载2.

权威敏捷产品经理（CSPO）企业培训

课程简介优秀的产品通常包括以下三个特征：第一：能够抓住用户痛点，帮助用户解决问题；第二：容易使用，极致的用户体验；第三：质量好、性能稳定。这是一个两天的面向产品经理的实训课程，课程旨在帮助学员掌握按照敏捷和互联网思维进行产品研发，打造用户喜爱的产品的思路及实践。课程内容涵盖了产品思维、用户需求挖掘、痛点分析，价值驱动、

APP产品经理岗位的具体内容（合集）

APP产品经理岗位的具体内容11、负责项目产品团队的管理工作，对项目产品团队考核目标负责;2、全面负责“工务园”所有产品，全方位负责其生命周期管理;3、按照产品管理相关的计划和规范，对产品版本的更新及发布负责，完善产品的各种技术文档;4、深刻理解业务需求并转化为系统需求，撰写产品需求文档和需求规格说明书;编写帮助文档、

热文推荐
  1. JavaScript系列从入门到精通系列第三篇：JavaScript基本语法(一)

    文章目录一：JavaScript基本语法1：JS注释(一)：JS多行注释(二)：JS单行注释(三)：JS中大小写(四)：分号问题(五)：空格和换行2：字面量和变量(一)：字面量(二)：变量(三)：如何声明变量(四)：如何给变量赋值(五)：标识符二：JS中6种数据类型(一)1：JS字符串(一)：JS字符串基本使用(二)：

  2. Ubuntu 安装 CUDA 与 OPENCL

    前言：最近需要做一些GPU并行计算，因而入坑CUDA和OPENCL，两者都有用到一些，刚好有点时间，同时记录一些学习过程，排掉一些坑，这篇是环境安装篇，基本跟着走就没什么问题，环境：ubuntu18.04/ubuntu20.04显卡：Nvidia一、CUDA安装1.查看电脑是否识别GPUlspci|grep-invid

  3. Liunx（Ubuntu20）常用指令

    -rwxr-xr-x,在Linux系统中权限是区分用户的，即用户、组用户、其他用户，第一位表示文件的类型，-代表文件，d代表目录，其他每个用户占三个字符用户、组用户、其他用户都是rwx形式，其中r表示读、w表示写、x表示可执行，-表示没有权限，拿用户组举例，r只能出现在第一个位置、w只能出现在第二个位置、x只能出现在第

  4. 在 CentOS 上安装 Docker Engine

    文章目录在CentOS上安装DockerEngine先决条件操作系统要求卸载旧版本安装方法使用rpm存储库安装设置存储库安装DockerEngine安装最新版本安装指定版本以非root用户身份管理Docker配置Docker以使用systemd启动参考官方文档：https://docs.docker.com/engin

  5. 阿里云服务器价格表，轻量和服务器最新活动价格表汇总

    租用阿里云服务器怎么收费？阿里云服务器配置不同一年价格也不同，阿里云2核2G3M带宽108元一年、2核4G4M带宽297.98元12个月，云服务器u1公网带宽可选1M到5M，系统盘为ESSD云盘40GB起，CPU内存配置可选2核2G、2核4G、4核8G、8核16G等配置，还有ECS计算型c7、通用型g7和内存型r7多C

  6. 【SLAM】前端-视觉里程计之对极几何

    文章目录【SLAM】前端-视觉里程计之对极几何1.对极几何2.本质矩阵及其求解3.单应矩阵及其求解3.三角测量4.思考4.1本质矩阵的自由度为多少4.2直接法求本质矩阵的过程涉及求解齐次线性方程，而对于齐次线性方程的解，要么只有零解，要么有无穷多个解，这里取哪一个解呢5.附录5.1相机成像模型【SLAM】前端-视觉里程

  7. 接口测试——接口协议抓包分析与mock_L1

    目录：接口测试价值与体系常见的接口协议接口测试用例设计postman基础使用postman实战练习1.接口测试价值与体系接口测试概念接口：不同的系统之间相互连接的部分，是一个传递数据的通道接口测试：检查数据的交换、传递和控制管理过程接口测试的价值传统的测试方法成本急剧上升测试效率下降分层测试体系越往上，发现Bug的时间

  8. CSS 布局 (三) 浮动、定位、多列布局

    6、浮动最初用于在文本块内浮动图像，float属性成为在网页上创建多列布局最常用的工具之一。随着flexbox和grid的出现，它现在又回到了最初的目的，正如本文所解释的那样。6.1浮动的背景引入float属性是为了允许web开发人员实现包含图像在文本列内浮动的布局，文本在其左侧或右侧环绕。就像你在报纸版面上看到的那样

  9. 函数扩展之——内存函数

    前言：小伙伴们又见面啦。本篇文章，我们将讲解C语言中比较重要且常用的内存函数，并尝试模拟实现它们的功能。让我们一起来学习叭。目录一.什么是内存函数二.内存函数有哪些1.memcpy（1）库函数memcpy（2）模拟实现memcpy2.memmove（1）库函数memmove（2）模拟实现memmove3.memset4