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

【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个数字必须是有序的&#xff0c;如果题目有要求&#xff0c;则进行堆排序即可。 还有比如求出全国玩韩信…...

【Spring从成神到升仙系列 四】从源码分析 Spring 事务的来龙去脉

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱敲代码的小黄&#xff0c;独角兽企业的Java开发工程师&#xff0c;CSDN博客专家&#xff0c;阿里云专家博主&#x1f4d5;系列专栏&#xff1a;Java设计模式、数据结构和算法、Kafka从入门到成神、Kafka从成神到升仙…...

使用Nginx反向代理OpenAI API

由于OpenAI的API在国内无法访问&#xff0c;所以可以通过海外服务器利用Nginx实现反向代理。 安装Nginx 这一步就不赘述了&#xff0c;不同的Linux系统安装方式略有不同&#xff0c;根据自己的服务器的系统自行百度即可。 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中断概述 处理器中的中断在处理器中&#xff0c;中断是一个过程&#xff0c;即CPU在正常执行程序的过程中&#xff0c;遇到外部/内部的紧急事件需要处理&#xff0c;暂时中止当前程序的…...

Flink进阶篇-CDC 原理、实践和优化采集到Doris中

简介 基于doris官方用doris构建实时仓库的思路&#xff0c;从flinkcdc到doris实时数仓的实践。 原文 Apache Flink X Apache Doris 构建极速易用的实时数仓架构 (qq.com) 前提-Flink CDC 原理、实践和优化 CDC 是什么 CDC 是变更数据捕获&#xff08;Change Data Captur…...

看完这篇 教你玩转渗透测试靶机vulnhub——My File Server: 1

Vulnhub靶机My File Server: 1渗透测试详解Vulnhub靶机介绍&#xff1a;Vulnhub靶机下载&#xff1a;Vulnhub靶机安装&#xff1a;Vulnhub靶机漏洞详解&#xff1a;①&#xff1a;信息收集&#xff1a;②&#xff1a;FTP匿名登入&#xff1a;③&#xff1a;SMB共享服务&#xf…...

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,大家好,今天为大家带来多线程案例--阻塞队列 这块知识点也很重要,要好好掌握呀~~~ &#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x…...

mysql的limit查询竟然有坑?

背景 最近项目联调的时候发现了分页查询的一个bug&#xff0c;分页查询总有数据查不出来或者重复查出。 数据库一共14条记录。 如果按照一页10条。那么第一页和第二页的查询SQL和和结果如下。 .png) 那么问题来了&#xff0c;查询第一页和第二页的时候都出现了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/时间复杂度/线性表&#xff1a;顺序表要求存储空间必须连续2.python模块导入&#xff1a;python3 -c ‘import sys;print(sys.path)’ 显示导入模块时会去哪些路径下查找3.进/线程&#xff1a;进/线程是不能随便创建&#xff0c;就像每招一个员工是有代价…...

异或相关算法

文章目录1. 异或的性质2. 题目一3. 题目二4. 题目三5. 题目四1. 异或的性质 我们知道&#xff0c;异或的定义是&#xff1a;相同为0&#xff0c;相异为1。所以也被称为无进位相加&#xff0c;根据这定义&#xff0c;我们可以得出三个性质&#xff1a; 1. N ^ N0。2. N ^ 0N。3…...

python 使用pyshp读写shp文件

安装 pip install pyshp 引入 import shapefile读取 sfshapefile.Reader("{路径名}",encodingutf-8) # 仅仅读取 shapes与shape shapessf.shapes() 返回值是一个列表&#xff0c;包含该文件中所有的”几何数据”对象shapesf.shape(0) Shape是第1个”几何数据”…...

eNSP FTP基础配置实验

关于本实验在本实验中&#xff0c;我们通过两台路由器来展示通过FTP在两台路由器之间传输文件。其中一台路由器AR2作为FTP服务器&#xff0c;另一台路由器AR1以FTP的方式登录AR2&#xff0c;并对AR2的文件系统进行一些更改。实验目的熟悉华为网络设备文件系统的管理。掌握华为网…...

堆及其多种接口与堆排序的实现

我们本期来讲解堆结构 目录 堆的结构 堆的初始化 堆的销毁 堆的插入 向上调整算法 堆的删除 向下调整算法 取堆顶元素 判断堆是否为空 堆中元素个数 堆排序 向下调整与向上调整效率计算 Top-K问题 全部代码 堆的结构 堆是一种用数组模拟二叉树的结构 逻辑结构是…...

JNI原理及常用方法概述

1.1 JNI(Java Native Interface) 提供一种Java字节码调用C/C的解决方案&#xff0c;JNI描述的是一种技术。 1.2 NDK(Native Development Kit) Android NDK 是一组允许您将 C 或 C&#xff08;“原生代码”&#xff09;嵌入到 Android 应用中的工具&#xff0c;NDK描述的是工具集…...

【Docker】之docker-compose的介绍与命令的使用

&#x1f341;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; 文章目录docker-compose简介docker-compose基础…...

水果新鲜程度检测系统(UI界面+YOLOv5+训练数据集)

摘要&#xff1a;水果新鲜程度检测软件用于检测水果新鲜程度&#xff0c;利用深度学习技术识别腐败或损坏的水果&#xff0c;以辅助挑拣出新鲜水果&#xff0c;支持实时在线检测。本文详细介绍水果新鲜程度检测系统&#xff0c;在介绍算法原理的同时&#xff0c;给出Python的实…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...