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

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问题&#xff1a; N个数找最大或者最小的前k个。 例子&#xff1a; 优质筛选&#xff08;店面的排名&#xff09; 10000个数&#xff0c;找出最大的前10个数 解决思路&#xff1a;建立大堆&#xff0c;然后pop9次 但是有些场景&#xff0c;上面的思路…...

接口自动化测试-Postman+Newman+Git+Jenkins实战集成(详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、Postman 创建…...

CMake 学习笔记 (Generator Expressions)

CMake 学习笔记 &#xff08;Generator Expressions&#xff09; Generator Expressions 可以认为是一种特殊的变量&#xff0c;它会在编译阶段求值。通常用在 target_link_libraries(), target_include_directories(), target_compile_definitions() 上。 用 Generator Expr…...

提高测试用例质量的6大注意事项

在软件测试中&#xff0c;经常会遇到测试用例设计不完整&#xff0c;用例没有完全覆盖需求等问题&#xff0c;这样往往容易造成测试工作效率低下&#xff0c;不能及时发现项目问题&#xff0c;无形中增加了项目风险。 因此提高测试用例质量&#xff0c;就显得尤为重要。一般来说…...

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) 题解 提供一种新的算法&#xff0c;kruskal重构树。 该算法重新构树&#xff0c;按边权排序每一条边…...

软件测试—支付功能测试

有人问过我这样一个问题&#xff1a;作为一个支付平台&#xff0c;接入了快钱、易宝或直连银行等多家的渠道&#xff0c;内在的产品流程是自己的。业内有什么比较好的测试办法&#xff0c;来测试各渠道及其支持的银行通道呢&#xff1f; 回答&#xff1a;对支付平台而言&#…...

自动化测试的统筹规划

背景 回顾以前自动化测试编写的经历&#xff0c;主要是以开发者自驱动的方式进行&#xff0c;测试的编写随心而动&#xff0c;没有规划&#xff0c;也没有章法&#xff0c;这样就面临如下的一些问题&#xff1a; 测试用例设计不到位&#xff0c;覆盖不全&#xff0c;或者不够…...

外键字段的增删改查、多表查询(子查询和连表查询、正反向、聚合查询、 分组查询、 F与Q查询)、django中如何开启事务

一、 外键字段的增删改查 1.多对多的外键增删改查图书和作者是多对多&#xff0c;借助于第三张表实现的&#xff0c;如果想绑定图书和作者的关系&#xff0c;本质上就是在操作第三方表2.如何操作第三张表问题&#xff1a;让你给图书添加一个作者&#xff0c;他俩的关系可是多对…...

【学习笔记】生成式AI(ChatGPT原理,大型语言模型)

ChatGPT原理剖析 语言模型 文字接龙 ChatGPT在测试阶段是不联网的。 ChatGPT背后的关键技术&#xff1a;预训练&#xff08;Pre-train&#xff09; 又叫自监督式学习&#xff08;Self-supervised Learning&#xff09;&#xff0c;得到的模型叫做基石模型&#xff08;Founda…...

【Opencv入门到项目实战】(三):图像腐蚀与膨胀操作

文章目录 1.腐蚀操作2.膨胀操作3.开运算和闭运算4.礼帽与黑帽5.梯度运算 1.腐蚀操作 腐蚀操作是图像处理中常用的一种形态学操作&#xff0c;我们通常用于去除图像中的噪声、分割连通区域、减小目标物体的尺寸等。腐蚀操作的原理是&#xff0c;在给定的结构元素下&#xff0c;…...

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 诊断入门介绍&#xff0c;会详细介绍诊断相关基础知识&#xff0c;如您对诊断实战有更高需求&#xff0c;…...

【iOS】json数据解析以及简单的网络数据请求

文章目录 前言一、json数据解析二、简单的网络数据请求三、实现访问API得到网络数据总结 前言 近期写完了暑假最后一个任务——天气预报&#xff0c;在里面用到了简单的网络数据请求以及json数据的解析&#xff0c;特此记录博客总结 一、json数据解析 JSON是一种轻量级的数据…...

Kubernetes客户端认证—— 基于ServiceAccount的JWTToken认证

1、概述 在 Kubernetes 官方手册中给出了 “用户” 的概念&#xff0c;Kubernetes 集群中存在的用户包括 “普通用户” 与 “ServiceAccount”&#xff0c; 但是 Kubernetes 没有普通用户的管理方式&#xff0c;通常只是将使用集群根证书签署的有效证书的用户都被视为合法用户。…...

45.ubuntu Linux系统安装教程

目录 一、安装Vmware 二、Linux系统的安装 今天开始了新的学习&#xff0c;Linux,下面是今天学习的内容。 一、安装Vmware 这里是在 Vmware 虚拟机中安装 linux 系统&#xff0c;所以需要先安装 vmware 软件&#xff0c;然 后再安装 Linux 系统。 所需安装文件&#xff1a;…...

Jmeter函数助手(一)随机字符串(RandomString)

一、目标 实现一个请求单次调用&#xff0c;请求体里多个集合中的相同参数&#xff08;zxqs&#xff09;值随机从序列{01、02、03、03、04、05、06、07、08}中取 若使用CSV数据文件、用户参数等参数化手段&#xff0c;单次执行请求&#xff0c;请求体里多个集合中的相同参数&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&#xff08;…...

机器学习入门之 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过程中&#xff0c;本机的内存等配置不足&#xff0c;启动较多的线程时&#xff0c;可以采用分布式运行。 在分布式运行的时候&#xff0c;jmeter会自动将脚本从master主机发送到remote主机上&#xff0c;所以不需要考虑将脚本拷贝到remote主机。但是jmeter…...

《OWASP代码审计》学习——注入漏洞审计

一、注入的概念 注入攻击允许恶意用户向应用程序添加或注入内容和命令&#xff0c;以修改其行为。这些类型的攻击是常见且广泛的&#xff0c;黑客很容易测试网站是否易受攻击&#xff0c;攻击者也很容易利用这些攻击。如今&#xff0c;它们在尚未更新的遗留应用程序中非常常见…...

使用小龙虾来操作猿编程的遥控车钾

一、什么是 Q 饱和运算&#xff1f; 1. 核心痛点&#xff1a;普通运算的 “数值回绕” 普通算术运算&#xff08;如 ADD/SUB&#xff09;溢出时&#xff0c;数值会按补码规则 “回绕”&#xff0c;导致结果完全错误&#xff1a; 示例&#xff1a;int8_t 类型最大值 127 1 → 结…...

【Python】CairoSVG实战:从SVG到多格式转换的完整指南

1. 为什么选择CairoSVG进行SVG转换 如果你经常需要处理矢量图形&#xff0c;肯定遇到过这样的场景&#xff1a;设计部门给你发来SVG文件&#xff0c;但你的应用场景需要PNG格式&#xff1b;或者需要把SVG图标批量导出为PDF文档。这时候CairoSVG就是你的瑞士军刀。 我在实际项目…...

Ubuntu 配置 Claude Code + MiniMax眯

先唠两句&#xff1a;参数就像餐厅点单 把API想象成一家餐厅的“后厨系统”。 ? 路径参数/dishes/{dish_id} -> 好比你要点“宫保鸡丁”这道具体的菜&#xff0c;它是菜单&#xff08;资源路径&#xff09;的一部分。查询参数/dishes?spicytrue&typeSichuan -> 好比…...

2026届毕业生推荐的五大降AI率平台解析与推荐

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek DeepSeek作为一款智能写作工具&#xff0c;对论文写作全过程能起到有效辅助作用&#xff0c…...

终极对比:NeverSink-Filter与其他掉落过滤器的核心优势

终极对比&#xff1a;NeverSink-Filter与其他掉落过滤器的核心优势 【免费下载链接】NeverSink-Filter This is a lootfilter for the game "Path of Exile". It hides low value items, uses a markup-scheme and sounds to highlight expensive gear and is based …...

Cogito-v1-preview-llama-3B入门必看:为什么3B参数能跑赢7B竞品?技术拆解

Cogito-v1-preview-llama-3B入门必看&#xff1a;为什么3B参数能跑赢7B竞品&#xff1f;技术拆解 你肯定听过不少大模型&#xff0c;动不动就是7B、13B甚至更大。参数越大&#xff0c;能力越强&#xff0c;这似乎是常识。但今天要聊的这个模型&#xff0c;可能要颠覆你的认知了…...

告别Hough和LSD:用Python+OpenCV实战EDLines直线检测,速度提升10倍

告别Hough和LSD&#xff1a;用PythonOpenCV实战EDLines直线检测&#xff0c;速度提升10倍 在计算机视觉领域&#xff0c;直线检测是许多高级任务的基础环节&#xff0c;从文档扫描到建筑测量&#xff0c;再到自动驾驶中的车道线识别&#xff0c;都离不开高效的直线提取。传统方…...

UniApp跨平台自定义消息语音播报实战指南

1. 为什么需要自定义消息语音播报 在移动应用开发中&#xff0c;消息推送是提升用户活跃度和留存率的重要手段。但普通的文字通知往往容易被用户忽略&#xff0c;特别是在商户收款、物流提醒、重要事件通知等场景下&#xff0c;语音播报能够更直接有效地触达用户。 举个例子&am…...

UGUI-视觉优化解决方案总结

文章目录前言UGUI的哪些组件可能需要性能优化&#xff1f;ScrollView的ViewPort可能有哪些解决方案?Image有可能包含哪些解决方案?Text有可能包含哪些解决方案?总结前言 这段时间接触了许多关于UGUI性能优化的内容&#xff0c;总结一下 UGUI的哪些组件可能需要性能优化&…...

告别有线!用ESP32和Arduino IDE打造你的专属蓝牙音箱(保姆级教程)

用ESP32打造高性价比蓝牙音箱&#xff1a;从硬件组装到音频调优全指南 你是否厌倦了市面上千篇一律的蓝牙音箱&#xff1f;想要一个既能展现个性又具备专业音质的无线音频设备&#xff1f;ESP32开发板加上一些基础电子元件&#xff0c;就能让你以不到200元的成本打造出媲美千元…...