当前位置: 首页 > news >正文

【优选算法】优先级队列 {优先级队列解决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问题,利用大小堆维护数据流的中位数}

一、经验总结 优先级队列&#xff08;堆&#xff09;&#xff0c;常用于在集合中筛选最值或解决TopK问题。 提示&#xff1a;对于固定序列的TopK问题&#xff0c;最优解决方案是快速选择算法&#xff0c;时间复杂度为O(N)比堆算法O(NlogK)更优&#xff1b;而对于动态维护数据流…...

11 IP协议 - IP协议头部

什么是 IP 协议 IP&#xff08;Internet Protocol&#xff09;是一种网络通信协议&#xff0c;它是互联网的核心协议之一&#xff0c;负责在计算机网络中路由数据包&#xff0c;使数据能够在不同设备之间进行有效的传输。IP协议的主要作用包括寻址、分组、路由和转发数据包&am…...

【java】【python】leetcode刷题记录--二叉树

144.二叉树的前序遍历 题目链接 前、中、后的遍历的递归做法实际上都是一样的&#xff0c;区别就是遍历操作的位置不同。 对于先序遍历&#xff0c;也就是先根&#xff0c;即把查看当前结点的操作放在最前面即可。 class Solution {public List<Integer> preorderTrav…...

EVA-CLIP实战

摘要 EVA-CLIP,这是一种基于对比语言图像预训练(CLIP)技术改进的模型,通过引入新的表示学习、优化和增强技术,显著提高了CLIP的训练效率和效果。EVA-CLIP系列模型在保持较低训练成本的同时,实现了与先前具有相似参数数量的CLIP模型相比更高的性能。特别地,文中提到的EV…...

限定法术施放目标

实现目标 法术只对特定 creature | gameobject 施放&#xff0c;否则无法施放 实现方法 conditions SourceTypeOrReferenceId&#xff1a;13&#xff08;CONDITION_SOURCE_TYPE_SPELL_IMPLICIT_TARGET&#xff09;SourceGroup&#xff1a;受条件影响的法术效果掩码&#xf…...

【通信原理】数字频带传输系统

二进制数字调制&#xff0c;解调原理&#xff1a;2ASK,2FSK 二进制数字调制&#xff0c;解调原理&#xff1a;2PSK,2DPSK 二进制数字已调制信号的功率谱 二进制数字调制系统的抗噪声性能 二进制调制系统的性能总结...

数据价值管理-数据验收标准

前情提要&#xff1a;数据价值管理是指通过一系列管理策略和技术手段&#xff0c;帮助企业把庞大的、无序的、低价值的数据资源转变为高价值密度的数据资产的过程&#xff0c;即数据治理和价值变现。第一讲介绍了业务架构设计的基本逻辑和思路。前面我们讲完了数据资产建设标准…...

vue3模板语法总结

1. 响应式数据 Vue 3中的数据是响应式的&#xff0c;即当数据发生变化时&#xff0c;视图会自动更新。这是通过使用JavaScript的getter和setter来实现的。 2. 组件化 Vue 3采用组件化开发方式&#xff0c;允许创建可复用的组件。 每个组件都有自己的作用域&#xff0c;并且…...

Spring Cloud 之 GateWay

前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff1a;https://www.captainbed.cn/z ChatGPT体验地址 文章目录 前言前言1、通过API网关访问服务2、Spring Cloud GateWay 最主要的功能就是路由…...

可转债全部历史因子数据,提供api支持

今天在写可转债系统&#xff0c;顺便下载了一下服务器的可转债数据&#xff0c;给大家研究使用 from trader_tool.stock_data import stock_datafrom trader_tool.lude_data_api import lude_data_apiimport osclass convertible_bond_back_test_system: 可转债回测系统…...

Python | C++ | MATLAB | Julia | R 市场流动性数学预期评估量

&#x1f3af;要点 &#x1f3af;市场流动性策略代码应用&#xff1a;&#x1f3af;动量策略&#xff1a;滚动窗口均值策略、简单移动平均线策略、指数加权移动平均线策略、相对强弱指数、移动平均线收敛散度交叉策略、三重指数平均策略、威廉姆斯 %R 策略 | &#x1f3af;均值…...

Android 常用开源库 MMKV 源码分析与理解

文章目录 前言一、MMKV简介1.mmap2.protobuf 二、MMKV 源码详解1.MMKV初始化2.MMKV对象获取3.文件摘要的映射4.loadFromFile 从文件加载数据5.数据写入6.内存重整7.数据读取8.数据删除9.文件回写10.Protobuf 实现1.序列化2.反序列化 12.文件锁1.加锁2.解锁 13.状态同步 总结参考…...

大模型高级 RAG 检索策略之流程与模块化

我们介绍了很多关于高级 RAG&#xff08;Retrieval Augmented Generation&#xff09;的检索策略&#xff0c;每一种策略就像是机器中的零部件&#xff0c;我们可以通过对这些零部件进行不同的组合&#xff0c;来实现不同的 RAG 功能&#xff0c;从而满足不同的需求。 今天我们…...

TCPListen客户端和TCPListen服务器

创建项目 TCPListen服务器 public Form1() {InitializeComponent();//TcpListener 搭建tcp服务器的类&#xff0c;基于socket套接字通信的//1创建服务器对象TcpListener server new TcpListener(IPAddress.Parse("192.168.107.83"), 3000);//2 开启服务器 设置最大…...

DDei在线设计器-属性编辑器

DDei-Core-属性编辑器 DDei-Core-属性编辑器插件包含了文本、大文本、数值、下拉、单选、勾选以及颜色等属性编辑。 图形和属性共同构成一个完整的定义&#xff0c;属性编辑器就是编辑属性值的控件。当选中图形实例时&#xff0c;属性面板就会展现当前实例的所有属性以及属性编…...

八字综合测算网整站源码程序/黄历/灵签/排盘/算命/生肖星座/日历网/周公解梦

八字综合测算网整站源码程序/黄历/灵签/排盘/算命/生肖星座/日历网/周公解梦 演示地址&#xff1a; https://s24.gvyun.com/ 手机端地址&#xff1a; https://ms24.gvyun.com/ 网站功能分类&#xff1a; 八字&#xff1a;八字测算&#xff1b;日干论命&#xff1b;称骨论命…...

C# WPF入门学习主线篇(十一)—— 布局管理

C# WPF入门学习主线篇&#xff08;十一&#xff09;—— 布局管理 欢迎来到C# WPF入门学习系列的第十一篇。在前面的文章中&#xff0c;我们已经探讨了WPF中的许多控件及其属性和事件。今天&#xff0c;我们将开启一个新的篇章——布局管理。布局管理是WPF中一个至关重要的概念…...

LabVIEW轴承试验机测控系统

开发了一种基于LabVIEW软件开发的大功率风电机组增速箱轴承试验机测控系统。系统主要用于模拟实际工况&#xff0c;进行轴承可靠性分析&#xff0c;以优化风电机组的性能和可靠性。通过高度自动化的测控系统&#xff0c;实现了对试验机的精确控制&#xff0c;包括速度、振动、温…...

0605 实际集成运算放大器的主要参数和对应用电路的影响

6.5.1 实际集成运放的主要参数 6.5.2 集成运放应用中的实际问题 6.5.2 集成运放应用中的实际问题...

艾宾浩斯winform单词系统+mysql

为用户提供集词典、题库、记忆单词功能于一体的应用&#xff0c;为用户提供目的性强、科学高效、多样化的记忆单词方法&#xff0c;使用户学习英语和记忆单词的效率得到提高 单词记忆模块 管理模块 查询单词 阅读英文 查看词汇 记忆单词 收藏单词 字段管理设置 统计 艾宾浩斯wi…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...