【TopK问题】——用堆实现
文章目录
- 一、TopK问题是什么
- 二、解决方法
- 三、时间复杂度
一、TopK问题是什么
TopK问题就是从1000个数中找出前K个最大的数或者最小的数这样的类似问题。
不过并不要求这k个数字必须是有序的,如果题目有要求,则进行堆排序即可。
还有比如求出全国玩韩信前十名等等,排出班级前十名也是TopK问题。
二、解决方法
采用堆的方式可以较快解决。
思路:如果需要排前k个最大的数,则需要建一个小堆
如果需要排前k个最小的数,则需要建一个大堆
假设现在需要排序前k个最大的数,则需要建立一个小堆。
建立小堆是拿n个数的前k个数来建立的。
不能把n个数全部建立成一个小堆,这样效率会大打折扣,因为通过向下调整建堆的时间复杂度是O(N),假如要从10亿个数字中排前50个最大的,那么建立一个10亿个数大小的堆,开销还是比较大的。
建立了一个小堆后,此时堆顶元素是最小的,
从第k+1个数开始,只要第K+1个数大于堆顶元素,就将该数字于堆顶元素进行交换,然后再向下调整。
这样做的结果是:只要我比堆顶元素大,我就进堆,如果我在堆中是比较大的,我就会“下沉”到堆底,(因为这是一个小堆)。
这样遍历多次后,原来堆中的元素会被换成新的一批更大一点的元素。
当我们遍历完n个数后,留在堆中的一定是前k个最大的数。
代码如下:
随机生成10个1000以内的数字,求这10个数字的最大的3个:
void Find_TopK(int* a, int n ,int k)
{assert(a!=NULL);assert(k > 0);int* topk = (int*)malloc(sizeof(int) * k);assert(topk);for (int i = 0; i < k; ++i){topk[i] = a[i];}//1.先建堆,向下调整建堆,现在是建小堆,那就找最大的前k个//把前k个抓起来,建立一个k大小的堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, k, i);}//2.然后从第k个开始,往堆里面插入int j = k;while (j < n){if (a[j] > topk[0]){topk[0] = a[j];AdjustDown(topk, k, 0);}j++;}printf("这10个数中最大的3个数为:\n");for (int i = 0; i < k; ++i){printf("%d ", topk[i]);}free(topk);topk = NULL;
}int main()
{srand(time(0));int a[100] = { 0 };printf("随机生成的10个1000以内的数为:\n");for (int i = 0; i < 10; ++i){a[i] = rand() % 1000;printf("%d ", a[i]);}printf("\n");int k = 3;int n = sizeof(a) / sizeof(a[0]);Find_TopK(a,n,k);return 0;
}
三、时间复杂度
建堆的时间复杂度:O(K)
遍历的时间复杂度:O(N-K)
每次遍历调整的时间复杂度:O(logK)
总的时间复杂度O(K+(N-K)logK) ≈ O(NlogK)
相关文章:
【TopK问题】——用堆实现
文章目录一、TopK问题是什么二、解决方法三、时间复杂度一、TopK问题是什么 TopK问题就是从1000个数中找出前K个最大的数或者最小的数这样的类似问题。 不过并不要求这k个数字必须是有序的,如果题目有要求,则进行堆排序即可。 还有比如求出全国玩韩信…...
【Spring从成神到升仙系列 四】从源码分析 Spring 事务的来龙去脉
👏作者简介:大家好,我是爱敲代码的小黄,独角兽企业的Java开发工程师,CSDN博客专家,阿里云专家博主📕系列专栏:Java设计模式、数据结构和算法、Kafka从入门到成神、Kafka从成神到升仙…...
使用Nginx反向代理OpenAI API
由于OpenAI的API在国内无法访问,所以可以通过海外服务器利用Nginx实现反向代理。 安装Nginx 这一步就不赘述了,不同的Linux系统安装方式略有不同,根据自己的服务器的系统自行百度即可。 OpenSSL创建证书 因为OpenAI的接口是https协议的&a…...
USB键盘实现——字符串描述符(四)
字符串描述符 字符串描述符内容解析和 HID鼠标 一致。 获取字符串描述符请求 标准设备请求 typedef struct __attribute__ ((packed)){union {struct __attribute__ ((packed)) {uint8_t recipient : 5; ///< Recipient type usb_request_recipient_t.uint8_t type …...
STM32的中断
目录 一、STM32中断概述 二、外部中断控制器EXTI 三、按键中断 四、串口中断 一、STM32中断概述 处理器中的中断在处理器中,中断是一个过程,即CPU在正常执行程序的过程中,遇到外部/内部的紧急事件需要处理,暂时中止当前程序的…...
Flink进阶篇-CDC 原理、实践和优化采集到Doris中
简介 基于doris官方用doris构建实时仓库的思路,从flinkcdc到doris实时数仓的实践。 原文 Apache Flink X Apache Doris 构建极速易用的实时数仓架构 (qq.com) 前提-Flink CDC 原理、实践和优化 CDC 是什么 CDC 是变更数据捕获(Change Data Captur…...
看完这篇 教你玩转渗透测试靶机vulnhub——My File Server: 1
Vulnhub靶机My File Server: 1渗透测试详解Vulnhub靶机介绍:Vulnhub靶机下载:Vulnhub靶机安装:Vulnhub靶机漏洞详解:①:信息收集:②:FTP匿名登入:③:SMB共享服务…...
OpenHarmony实战STM32MP157开发板 “控制” Hi3861开发板 -- 中篇
一、前言 我们在 OpenHarmony实战STM32MP157开发板 “控制” Hi3861开发板 – 上篇 中介绍到了,App面板的开发,以及JS API接口的开发和调用。 那么本篇文章,会详解:BearPi-HM Nano开发板,如何实现数据上报和指令接收响应的。 看到这里,可能有同学可能已经知道思路了,因…...
【数据结构初阶】单链表
目录一、思路>>>>>>>>>>>>过程<<<<<<<<<<<<<<<1.打印2.尾插3.尾删4.头插5.头删6.查找7.指定位置后插入8.指定位置后删除9.链表的销毁二、整个程序1.SLTlist.c2.SLTlist.c一、思路 #define …...
多线程代码案例-阻塞队列
hi,大家好,今天为大家带来多线程案例--阻塞队列 这块知识点也很重要,要好好掌握呀~~~ 🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸&#x…...
mysql的limit查询竟然有坑?
背景 最近项目联调的时候发现了分页查询的一个bug,分页查询总有数据查不出来或者重复查出。 数据库一共14条记录。 如果按照一页10条。那么第一页和第二页的查询SQL和和结果如下。 .png) 那么问题来了,查询第一页和第二页的时候都出现了11,12,13的记录…...
【Docker】MAC电脑下的Docker操作
文章目录安装Docker部署mysql 一主一从登录ChatGPT搞方案本地创建一个文件夹编辑docker-compose.yml文件启动检查并编排容器验证基于command的my.cnf配置的加载主数据库建一个用户给子数据库用于主从复制启动主从同步安装Docker 官网地址 https://www.docker.com/ 下载安装 验…...
【Python3】matplotlib,模块,进/线程,文件/xml,百度人脸api,hal/aiohttp/curl
文章目录1.matplotlib/时间复杂度/线性表:顺序表要求存储空间必须连续2.python模块导入:python3 -c ‘import sys;print(sys.path)’ 显示导入模块时会去哪些路径下查找3.进/线程:进/线程是不能随便创建,就像每招一个员工是有代价…...
异或相关算法
文章目录1. 异或的性质2. 题目一3. 题目二4. 题目三5. 题目四1. 异或的性质 我们知道,异或的定义是:相同为0,相异为1。所以也被称为无进位相加,根据这定义,我们可以得出三个性质: 1. N ^ N0。2. N ^ 0N。3…...
python 使用pyshp读写shp文件
安装 pip install pyshp 引入 import shapefile读取 sfshapefile.Reader("{路径名}",encodingutf-8) # 仅仅读取 shapes与shape shapessf.shapes() 返回值是一个列表,包含该文件中所有的”几何数据”对象shapesf.shape(0) Shape是第1个”几何数据”…...
eNSP FTP基础配置实验
关于本实验在本实验中,我们通过两台路由器来展示通过FTP在两台路由器之间传输文件。其中一台路由器AR2作为FTP服务器,另一台路由器AR1以FTP的方式登录AR2,并对AR2的文件系统进行一些更改。实验目的熟悉华为网络设备文件系统的管理。掌握华为网…...
堆及其多种接口与堆排序的实现
我们本期来讲解堆结构 目录 堆的结构 堆的初始化 堆的销毁 堆的插入 向上调整算法 堆的删除 向下调整算法 取堆顶元素 判断堆是否为空 堆中元素个数 堆排序 向下调整与向上调整效率计算 Top-K问题 全部代码 堆的结构 堆是一种用数组模拟二叉树的结构 逻辑结构是…...
JNI原理及常用方法概述
1.1 JNI(Java Native Interface) 提供一种Java字节码调用C/C的解决方案,JNI描述的是一种技术。 1.2 NDK(Native Development Kit) Android NDK 是一组允许您将 C 或 C(“原生代码”)嵌入到 Android 应用中的工具,NDK描述的是工具集…...
【Docker】之docker-compose的介绍与命令的使用
🍁博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 文章目录docker-compose简介docker-compose基础…...
水果新鲜程度检测系统(UI界面+YOLOv5+训练数据集)
摘要:水果新鲜程度检测软件用于检测水果新鲜程度,利用深度学习技术识别腐败或损坏的水果,以辅助挑拣出新鲜水果,支持实时在线检测。本文详细介绍水果新鲜程度检测系统,在介绍算法原理的同时,给出Python的实…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
