【优选算法】优先级队列 {经验总结:优先级队列解决TopK问题,利用大小堆维护数据流中的中位数;相关编程题解析}

本文主要是介绍【优选算法】优先级队列 {经验总结:优先级队列解决TopK问题,利用大小堆维护数据流中的中位数;相关编程题解析},希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、经验总结

优先级队列(堆),常用于在集合中筛选最值或解决TopK问题。

提示:对于固定序列的TopK问题,最优解决方案是快速选择算法,时间复杂度为O(N)比堆算法O(NlogK)更优;而对于动态维护数据流中的TopK,最优解决方案是堆算法,每次添加数据后筛选,时间复杂度为O(logK)比快速选择算法O(N)更优;

优先级队列如何解决TopK问题?

  1. 创建一个大小为K的堆
  2. 循环
    1. 将数组中的元素依次进堆
    2. 判断堆中的元素个数是否大于K,如果大于K就pop弹出堆顶元素
  3. 将数组中的所有元素全部筛选一遍后,堆中剩余的K个元素就是最大(小)的K个元素

TopK问题选用大根堆还是小根堆?

  • 如果要选出最大的K个数,就选用小根堆;
  • 如果要选出最小的K个数,就选用大根堆;

利用大小堆维护数据流中的中位数

  1. 创建一个大堆left用于存储数据流的前一半(升序),一个小堆right用于存储后一半
  2. 控制left的元素个数m和right的元素个数n满足:m==n或m==n+1
  3. 数据流的中位数:当m==n时,mid=(left.top()+right.top())/2;当m==n+1时,mid=left.top();
  4. 新增元素:将新元素与left.top()(或right.top())比较,决定加入left还是right。完成插入后,记得调整两个堆的元素个数使其满足规则。

二、相关编程题

2.1 最后一块石头的重量

题目链接

1046. 最后一块石头的重量 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

利用堆结构筛选最大值

编写代码

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for(auto e : stones) heap.push(e);while(heap.size() >= 2){int s1 = heap.top();heap.pop();int s2 = heap.top();heap.pop();if(s1 > s2) heap.push(s1-s2);}if(heap.size() == 0) return 0;else return heap.top();}
};

2.2 数据流中的第 K 大元素

题目链接

703. 数据流中的第 K 大元素 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述
这道题更适合使用堆解决,因为add函数插入一个数字后返回当前数据中的第K大的元素,如果使用快速选则算法,复杂度为O(N);而使用堆算法,复杂度为O(logK)

编写代码

class KthLargest {priority_queue<int, vector<int>, greater<int>> _heap;int _k;
public:KthLargest(int k, vector<int>& nums) {_k = k;for(auto e : nums) add(e);}int add(int val) {_heap.push(val);if(_heap.size() > _k)_heap.pop();return _heap.top();}
};

2.3 前K个高频单词

题目链接

692. 前K个高频单词 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {typedef pair<string, int> PSI;struct Cmp{bool operator()(const PSI &left, const PSI &right){if(left.second != right.second) //出现频次不同,选出高频单词,按照小根堆的方式排列return left.second > right.second;elsereturn left.first < right.first; //出现频次相同,按字典序排序,按照大根堆的方式排列}};
public:vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string, int> hash;priority_queue<PSI, vector<PSI>, Cmp> heap;vector<string> ret(k);//统计所有单词的出现频次for(auto &str:words){++hash[str];} //用一个大小为k的堆筛选TopKfor(auto &psi:hash){heap.push(psi);if(heap.size() > k)heap.pop();}//将结果倒着放入数组for(int i = k-1; i >= 0; --i){ret[i] = heap.top().first;heap.pop();}return ret;}
};

2.4 数据流的中位数

题目链接

295. 数据流的中位数 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class MedianFinder {priority_queue<int> left; //大根堆priority_queue<int, vector<int>, greater<int>> right; //小根堆
public:MedianFinder() {}void addNum(int num) {if(left.size() > right.size()) //m > n{int x = left.top();if(num <= x){left.push(num);left.pop();right.push(x);}else{right.push(num);}}else //m == n{int y = right.empty()? 0:right.top();if(right.empty() || num < y){left.push(num);}else{right.push(num);right.pop();left.push(y);}}}double findMedian() {if(left.size() > right.size()) //m > nreturn (double)left.top();else //m == nreturn (left.top()+right.top())/2.0;}
};

这篇关于【优选算法】优先级队列 {经验总结:优先级队列解决TopK问题,利用大小堆维护数据流中的中位数;相关编程题解析}的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032775

相关文章

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

JavaScript Array.from及其相关用法详解(示例演示)

《JavaScriptArray.from及其相关用法详解(示例演示)》Array.from方法是ES6引入的一个静态方法,用于从类数组对象或可迭代对象创建一个新的数组实例,本文将详细介绍Array... 目录一、Array.from 方法概述1. 方法介绍2. 示例演示二、结合实际场景的使用1. 初始化二

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时