当前位置: 首页 > 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;它们在尚未更新的遗留应用程序中非常常见…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...