TopK问题
topK问题:
N个数找最大或者最小的前k个。
例子:
优质筛选(店面的排名)
10000个数,找出最大的前10个数
解决思路:建立大堆,然后pop9次
但是有些场景,上面的思路解决不了,比如N非常大
比如:N=10亿,k=100
这里的空间就会不够:
10亿个整数,需要多少空间——》1024*1024*1024byte ——》 4G
数据多时,内存不够,则会存入磁盘文件中(磁盘中的数据不可以随机访问,所以不可以建堆)
终极解决思路:
建立k个数的小堆
后面N-K个数有,一次比较,如果比堆顶的数据大,就替换他进堆
不断替换堆顶值,然后向下调整
最后,这个小堆的值就是最大的前k个数
void CreatNDate(){ int n = 1000;srand(time(0));const char * file = "data.txt";FILE *fin = fopen(file,"w");if(fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand()%1000000;fprintf(fin,"%d\n",x);} }void PrintTopK(int k){const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* kminheap = (int *)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}//取前k个数,建立小堆for (int i = (k-1-1)/2; i >= 0; i--){AdjustDown(kminheap,k,i);}//读取剩下的数,谁比堆顶元素大,谁踢出堆顶元素然后进入这个堆。int val = 0;while (!feof(fout)){fscanf(fout, "%d", &val);if (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d\n", kminheap[i]);}}
总结:
此方法的时间复杂度为:k+(n-k)*logk.
相关文章:
TopK问题
topK问题: N个数找最大或者最小的前k个。 例子: 优质筛选(店面的排名) 10000个数,找出最大的前10个数 解决思路:建立大堆,然后pop9次 但是有些场景,上面的思路…...
接口自动化测试-Postman+Newman+Git+Jenkins实战集成(详细)
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 1、Postman 创建…...
CMake 学习笔记 (Generator Expressions)
CMake 学习笔记 (Generator Expressions) Generator Expressions 可以认为是一种特殊的变量,它会在编译阶段求值。通常用在 target_link_libraries(), target_include_directories(), target_compile_definitions() 上。 用 Generator Expr…...
提高测试用例质量的6大注意事项
在软件测试中,经常会遇到测试用例设计不完整,用例没有完全覆盖需求等问题,这样往往容易造成测试工作效率低下,不能及时发现项目问题,无形中增加了项目风险。 因此提高测试用例质量,就显得尤为重要。一般来说…...
2023牛客暑期多校训练营6 A-Tree (kruskal重构树))
文章目录 题目大意题解参考代码 题目大意 ( 0 ≤ a i ≤ 1 ) , ( 1 ≤ c o s t i ≤ 1 0 9 ) (0\leq a_i\leq 1),(1 \leq cost_i\leq 10^9) (0≤ai≤1),(1≤costi≤109) 题解 提供一种新的算法,kruskal重构树。 该算法重新构树,按边权排序每一条边…...
软件测试—支付功能测试
有人问过我这样一个问题:作为一个支付平台,接入了快钱、易宝或直连银行等多家的渠道,内在的产品流程是自己的。业内有什么比较好的测试办法,来测试各渠道及其支持的银行通道呢? 回答:对支付平台而言&#…...
自动化测试的统筹规划
背景 回顾以前自动化测试编写的经历,主要是以开发者自驱动的方式进行,测试的编写随心而动,没有规划,也没有章法,这样就面临如下的一些问题: 测试用例设计不到位,覆盖不全,或者不够…...
外键字段的增删改查、多表查询(子查询和连表查询、正反向、聚合查询、 分组查询、 F与Q查询)、django中如何开启事务
一、 外键字段的增删改查 1.多对多的外键增删改查图书和作者是多对多,借助于第三张表实现的,如果想绑定图书和作者的关系,本质上就是在操作第三方表2.如何操作第三张表问题:让你给图书添加一个作者,他俩的关系可是多对…...
【学习笔记】生成式AI(ChatGPT原理,大型语言模型)
ChatGPT原理剖析 语言模型 文字接龙 ChatGPT在测试阶段是不联网的。 ChatGPT背后的关键技术:预训练(Pre-train) 又叫自监督式学习(Self-supervised Learning),得到的模型叫做基石模型(Founda…...
【Opencv入门到项目实战】(三):图像腐蚀与膨胀操作
文章目录 1.腐蚀操作2.膨胀操作3.开运算和闭运算4.礼帽与黑帽5.梯度运算 1.腐蚀操作 腐蚀操作是图像处理中常用的一种形态学操作,我们通常用于去除图像中的噪声、分割连通区域、减小目标物体的尺寸等。腐蚀操作的原理是,在给定的结构元素下,…...
Autosar诊断系列介绍20 - UDS应用层P2Server/P2Client等时间参数解析
本文框架 1. 前言2.几个时间参数含义2.1 P2Client与P2Server2.2 P2*Client与P2*Server2.3 P3Client_Phys与P3Client_Func2.4 S3Client与S3Server 1. 前言 本系列Autosar 诊断入门介绍,会详细介绍诊断相关基础知识,如您对诊断实战有更高需求,…...
【iOS】json数据解析以及简单的网络数据请求
文章目录 前言一、json数据解析二、简单的网络数据请求三、实现访问API得到网络数据总结 前言 近期写完了暑假最后一个任务——天气预报,在里面用到了简单的网络数据请求以及json数据的解析,特此记录博客总结 一、json数据解析 JSON是一种轻量级的数据…...
Kubernetes客户端认证—— 基于ServiceAccount的JWTToken认证
1、概述 在 Kubernetes 官方手册中给出了 “用户” 的概念,Kubernetes 集群中存在的用户包括 “普通用户” 与 “ServiceAccount”, 但是 Kubernetes 没有普通用户的管理方式,通常只是将使用集群根证书签署的有效证书的用户都被视为合法用户。…...
45.ubuntu Linux系统安装教程
目录 一、安装Vmware 二、Linux系统的安装 今天开始了新的学习,Linux,下面是今天学习的内容。 一、安装Vmware 这里是在 Vmware 虚拟机中安装 linux 系统,所以需要先安装 vmware 软件,然 后再安装 Linux 系统。 所需安装文件:…...
Jmeter函数助手(一)随机字符串(RandomString)
一、目标 实现一个请求单次调用,请求体里多个集合中的相同参数(zxqs)值随机从序列{01、02、03、03、04、05、06、07、08}中取 若使用CSV数据文件、用户参数等参数化手段,单次执行请求,请求体里多个集合中的相同参数&a…...
SpringCloud之微服务API网关Gateway介绍
文章目录 1 微服务API网关Gateway1.1 网关简介1.2 Spring Cloud Gateway介绍1.3 Gateway特性1.4 Gateway核心概念1.4.1 路由1.4.1.1 定义1.4.1.2 动态路由 1.4.2 断言1.4.2.1 默认断言1.4.2.2 自定义Predicate 1.4.3 过滤器1.4.3.1 默认过滤器1.4.3.2 自定义Filter(…...
机器学习入门之 pandas
pandas 有三种数据结构 一种是 Series 一种是 Dataframe import pandas as pd import numpy as np score np.random.randint(0,100,[10,5])score[0,0] 100Datascore pd.DataFrame(score)subject ["语文","数学","英语","物理&quo…...
Django之JWT库与SimpleJWT库的使用
Django之JWT库与SimpleJWT库的使用 JWTJWT概述头部(header)载荷(payload)签名(signature) Django使用JWT说明jwt库的使用安装依赖库配置settings.py文件配置urls.py文件创建视图配置权限 SimpleJWT库的使用安装SimpleJWT库配置Django项目配置路由创建用户接口测试身份认证自定义…...
Jmeter远程服务模式运行时引用csv文件的路径配置
问题 在使用jmeter过程中,本机的内存等配置不足,启动较多的线程时,可以采用分布式运行。 在分布式运行的时候,jmeter会自动将脚本从master主机发送到remote主机上,所以不需要考虑将脚本拷贝到remote主机。但是jmeter…...
《OWASP代码审计》学习——注入漏洞审计
一、注入的概念 注入攻击允许恶意用户向应用程序添加或注入内容和命令,以修改其行为。这些类型的攻击是常见且广泛的,黑客很容易测试网站是否易受攻击,攻击者也很容易利用这些攻击。如今,它们在尚未更新的遗留应用程序中非常常见…...
打造自己的信道编码工具箱——Turbo、LDPC、极化码三合一
作者:绳匠_ZZ0从零开始,把现代编码三巨头整合到一个C语言项目中,实现编码、译码、误码率测试一体化📦 前言:为什么我要做这个工具箱?过去几个月,我陆续学习了Turbo码、LDPC码和极化码。每次写代…...
Dify二次开发实战:定制化LLM接入与认证改造指南
1. 为什么需要定制化LLM接入 在企业级大模型应用开发中,直接使用原生开源模型往往存在诸多限制。我去年参与过一个金融行业的智能客服项目,客户明确要求所有API调用必须经过三重认证。这就是为什么我们需要对Dify这类工具进行二次开发。 标准OpenAI接口协…...
Umi-OCR终极指南:三步实现免费离线OCR,高效处理海量文档
Umi-OCR终极指南:三步实现免费离线OCR,高效处理海量文档 【免费下载链接】Umi-OCR OCR software, free and offline. 开源、免费的离线OCR软件。支持截屏/批量导入图片,PDF文档识别,排除水印/页眉页脚,扫描/生成二维码…...
智能验证码获取:从零构建自动化注册系统的技术深度解析
智能验证码获取:从零构建自动化注册系统的技术深度解析 【免费下载链接】cursor-free-vip [Support 0.45](Multi Language 多语言)自动注册 Cursor Ai ,自动重置机器ID , 免费升级使用Pro 功能: Youve reached your tr…...
AI Agent集成实时口罩检测:智能机器人视觉系统设计
AI Agent集成实时口罩检测:智能机器人视觉系统设计 1. 引言 在智能机器人快速发展的今天,视觉感知能力成为机器人智能化水平的关键指标。特别是在公共场所服务、医疗辅助、安防巡检等场景中,机器人需要具备实时识别和响应能力。口罩检测作为…...
AI技术在搜索引擎优化中的关键词选择与提升策略
本文针对AI技术在搜索引擎优化(SEO)中的关键词选择与提升策略进行了全面探讨。首先,分析了AI如何通过深度学习与数据挖掘,帮助营销人员发现潜在的高效关键词。接着,阐述了结合市场趋势和用户行为,实现关键词…...
MediaCreationTool.bat:终极Windows安装自动化工具,三步完成系统部署
MediaCreationTool.bat:终极Windows安装自动化工具,三步完成系统部署 【免费下载链接】MediaCreationTool.bat Universal MCT wrapper script for all Windows 10/11 versions from 1507 to 21H2! 项目地址: https://gitcode.com/gh_mirrors/me/MediaC…...
微软开源TTS模型VibeVoice部署:网页界面推理,支持超长语音
微软开源TTS模型VibeVoice部署:网页界面推理,支持超长语音 1. 引言 1.1 语音合成新突破 在当今数字内容爆炸式增长的时代,语音合成技术正变得越来越重要。微软最新开源的VibeVoice TTS模型带来了革命性的进步,它能够生成长达96…...
Windows环境下EMQX守护进程的自动化监控与恢复方案
1. 为什么需要EMQX守护进程监控方案 EMQX作为一款开源的MQTT消息中间件,在物联网和实时通信领域应用广泛。但在实际生产环境中,尤其是在Windows服务器上长期运行时,经常会遇到服务意外退出的情况。我自己在运维一个老旧项目时就深有体会——由…...
Clawdbot汉化版代码实例:crontab定时任务+每日天气报告Telegram推送
Clawdbot汉化版代码实例:crontab定时任务每日天气报告Telegram推送 1. 项目概述与使用场景 Clawdbot汉化版是一个可以在微信、WhatsApp、Telegram等社交平台中使用的智能对话助手。与传统的在线AI服务不同,Clawdbot完全运行在用户自己的设备上…...
