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

堆的应用-----Top k 问题

目录

前言

Topk问题

1.问题描述

2.解决方法

3.代码实现(C/C++) 


前言

在人工智能算法岗位的面试中,TopK是问得最多的几个问题之一:

到底有几种方法?

这些方案里蕴含的优化思路究竟是怎么样的?

为啥TopK这么受欢迎呢?究其原因,还是因为它不仅在AI领域广泛应用,比如max pooling,mAP计算等;还涵盖了算法专业的很多必备知识,比如快速排序,二分查找,分治减治,大小顶堆等;一些适当的变换,还可以考察应聘者的思维灵活度。

下面的文章转自架构师之路,是笔者见过此类文章中总结的最透彻的一篇,为了行文流畅,文章有增删。

        前段时间我们学习过了数据结构堆以及堆排序算法,堆是一种完全二叉树,那今天我们学习堆的应用,解决topk问题,下面就一起来看看吧。

(相关链接:数据结构-----堆(完全二叉树)-CSDN博客)

Topk问题

1.问题描述

从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。

看上去是不是非常直白明了呢?那确实是,但是怎么去解决这个问题?当然我们会想到排序去处理,把这个数组进行排序,然后直接就可以找到了。但是排序的话会把一些不必要的数进行排序处理,也就是说时间复杂度会比较大,但是如果我们单单对前k个大的数字进行单独处理,那效果是不是更好呢?下面我们就看一看堆是怎么实现的。

2.解决方法

我们获取到当前的数组的时候,然后就创建一个大堆,如图所示,其特点就是上面的元素比下面的元素要大。创建好大堆之后,我们就可以进行后继处理。当前大堆最大的元素就是在第一个位置,我们把第一个位置(最大元素),与最后一个位置的元素进行位置交换,然后把最后一个位置的元素踢出当前的堆,在前面n-1个元素里面再找最大值即可,依次重复以上的操作,执行k次就完成了问题的解决。

3.代码实现(C/C++) 

#include<stdio.h>
#include<stdlib.h>//交换数字
void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}//向下调整
void adjust_down(int* arr, int par, int n) {int child = par * 2 + 1;while (child < n) {if (arr[child] < arr[child + 1] && child + 1 < n)child++;if (arr[par] < arr[child]) {swap(&arr[par], &arr[child]);par = child;child = par * 2 + 1;}elsebreak;}
}//函数接口
void Top_k(int* arr, int n,int k) {//先创建这个堆for (int i = (n - 1) / 2; i >= 0; i--) {adjust_down(arr, i, n);}//然后就是获取当前堆中的最大值int end = n - 1;int count = 0;while (count < k) {//当前最大值下标为0,把最大值的数与最后一个数进行交换swap(&arr[end], &arr[0]);//end--,把最大值踢出当前堆,然后从剩下的n-1个数字的堆继续找最大值adjust_down(arr, 0, end);end--;count++;}printf("前%d大的数是:\n", k);for (int i = n - 1; i > n - 1 - count; i--) {printf("%d ", arr[i]);}
}int main() {int arr[] = { 5,1,4,7,8,9,3,4,5,6,7,10,55 };int k = 3;Top_k(arr, sizeof(arr) / sizeof(int), k);
}

以上就是本期的全部内容了,我们下次见!

分享一张壁纸:

相关文章:

堆的应用-----Top k 问题

目录 前言 Topk问题 1.问题描述 2.解决方法 3.代码实现&#xff08;C/C&#xff09; 前言 在人工智能算法岗位的面试中&#xff0c;TopK是问得最多的几个问题之一&#xff1a; 到底有几种方法&#xff1f; 这些方案里蕴含的优化思路究竟是怎么样的&#xff1f; 为啥T…...

11月14日星期二今日早报简报微语报早读

11月14日星期二&#xff0c;农历十月初二&#xff0c;早报微语早读。 1、江西南城县&#xff1a;限时发放购房补贴政策&#xff0c;三孩家庭每平方米最高补贴500元&#xff1b; 2、2023年中国内地电影市场累计票房突破500亿元&#xff1b; 3、市场监管总局&#xff1a;在全国…...

Spark读取excel文件

文章目录 一、excel数据源转成csv二、Spark读取csv文件(一)启动spark-shell(二)读取csv生成df(三)查看df内容一、excel数据源转成csv 集群bigdata - ubuntu: 192.168.191.19master(bigdata1) - centos: 192.168.23.78 slave1(bigdata2) - centos: 192.168.23.79 slave2(b…...

LLM大语言模型(典型ChatGPT)入门指南

文章目录 一、基础概念学习篇1.1 langchain视频学习笔记1.2 Finetune LLM视频学习笔记 二、实践篇2.1 预先下载模型&#xff1a;2.2 LangChain2.3 Colab demo2.3 text-generation-webui 三、国内项目实践langchain-chatchat 一、基础概念学习篇 1.1 langchain视频学习笔记 lan…...

Spring IOC - Bean的生命周期之实例化

在Spring启动流程文章中讲到&#xff0c;容器的初始化是从refresh方法开始的&#xff0c;其在初始化的过程中会调用finishBeanFactoryInitialization方法。 而在该方法中则会调用DefaultListableBeanFactory#preInstantiateSingletons方法&#xff0c;该方法的核心作用是初始化…...

前端 BUG 总结

文章目录 CSS 样式1、Chrome 89 版本期不再支持 /deep/&#xff0c;请勿使用嵌套 /deep/2、圆角按钮 button 点击后出现矩形框线3、怪异模式4、border 1 像素在手机上显示问题5、文本溢出问题 JavaScript 脚本1、移动端点击穿透2、使用parseInt时必须补全第二个参数 radix3、有…...

【蓝桥杯软件赛 零基础备赛20周】第3周——填空题

报名明年4月蓝桥杯软件赛的同学们&#xff0c;如果你是大一零基础&#xff0c;目前懵懂中&#xff0c;不知该怎么办&#xff0c;可以看看本博客系列&#xff1a;备赛20周合集 20周的完整安排请点击&#xff1a;20周计划 文章目录 00. 2023年第14届参赛数据0. 上一周答疑1. 填空…...

Pytorch自动混合精度的计算:torch.cuda.amp.autocast

1 autocast介绍 1.1 什么是AMP? 默认情况下&#xff0c;大多数深度学习框架都采用32位浮点算法进行训练。2017年&#xff0c;NVIDIA研究了一种用于混合精度训练的方法&#xff0c;该方法在训练网络时将单精度&#xff08;FP32&#xff09;与半精度(FP16)结合在一起&#xff…...

一文看懂香港优才计划和高才通计划的区别和优势?如何选?

一文看懂香港优才计划和高才通计划的区别和优势&#xff1f;如何选&#xff1f; 为什么很多人都渴望有个香港身份&#xff1f; 英文这里和内地文化相近&#xff0c;语言相通&#xff0c;同时税率较低、没有外汇管制&#xff0c;有稳定金融体制和良好的营商环境&#xff0c;诸多…...

DTC Network旗下代币DSTC大蒜头即将上线,市场热度飙升

全球数字资产领导者DTC Network宣布其代币DSTC&#xff08;大蒜头&#xff09;即将于近期上线&#xff0c;引发市场广泛关注。DTC Network以其创新性的区块链技术和多维度的网络构建&#xff0c;致力于打造一个融合Web3.0、元宇宙和DAPP应用的去中心化聚合公共平台&#xff0c;…...

高通SDX12:ASoC 音频框架浅析

一、简介 ASoC–ALSA System on Chip ,是建立在标准ALSA驱动层上,为了更好地支持嵌入式处理器和移动设备中的音频Codec的一套软件体系。 本文基于高通SDX12平台,对ASoC框架做一个分析。 二、整体框架 1. 硬件层面 嵌入式Linux设备的Audio subsystem可以划分为Machine(板…...

国际化:i18n

什么是国际化&#xff1f; 国际化也称作i18n&#xff0c;其来源是英文单词 internationalization的首末字符和n&#xff0c;18为中间的字符数。由于软件发行可能面向多个国家&#xff0c;对于不同国家的用户&#xff0c;软件显示不同语言的过程就是国际化。通常来讲&#xff0…...

【机器学习5】无监督学习聚类

相比于监督学习&#xff0c; 非监督学习的输入数据没有标签信息&#xff0c; 需要通过算法模型来挖掘数据内在的结构和模式。 非监督学习主要包含两大类学习方法&#xff1a; 数据聚类和特征变量关联。 1 K均值聚类及优化及改进模型 1.1 K-means 聚类是在事先并不知道任何样…...

风景照片不够清晰锐利,四招帮你轻松解决

我们大家在拍摄风景照的时候都希望能够拍摄出清晰锐利的照片。可能会有人问&#xff1a;“什么是锐利&#xff1f;”我们可以从锐度来给大家简单解说下。锐度是反映图片平面清晰度和图像边缘对比度的一个参数。锐度较高的画面&#xff0c;微小的细节部分也会表现得很清晰&#…...

List中的迭代器实现【C++】

List中的迭代器实现【C】 一. list的结构二. 迭代器的区别三. 迭代器的实现i. 类的设计ii. 重载iii. !重载iiii. begin()iiiii. end()iiiii. operator* 四.测试五. const迭代器的实现i. 实现ii 优化实现 六. 整体代码 一. list的结构 其实按照习惯来说&#xff0c;应该要专门出…...

VB.NET三层之用户查询窗体

目录 前言: 过程: UI层代码展示: BLL层代码展示: DAL层代码展示: 查询用户效果图:​ 总结: 前言: 想要对用户进行查询&#xff0c;需要用到控件DataGrideView&#xff0c;通过代码的形式将数据库表中的数据显示在DataGrideview控件中&#xff0c;不用对DatGridView控件…...

Django之路由层

文章目录 路由匹配语法路由配置注意事项转换器注册自定义转化器 无名分组和有名分组无名分组有名分组 反向解析简介普通反向解析无名分组、有名分组之反向解析 路由分发简介为什么要用路由分发&#xff1f;路由分发实现 伪静态的概念名称空间虚拟环境什么是虚拟环境&#xff1f…...

【06】VirtualService高级流量功能

5.3 weight 部署demoapp v10和v11版本 --- apiVersion: apps/v1 kind: Deployment metadata:labels:app: demoappv10version: v1.0name: demoappv10 spec:progressDeadlineSeconds: 600replicas: 3selector:matchLabels:app: demoappversion: v1.0template:metadata:labels:app…...

322. 零钱兑换

给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -1 。 你可以认为每种硬币的数量是无限的。 示…...

【大模型-第一篇】在阿里云上部署ChatGLM3

前言 好久没写博客了&#xff0c;最近大模型盛行&#xff0c;尤其是ChatGLM3上线&#xff0c;所以想部署试验一下。 本篇只是第一篇&#xff0c;仅仅只是部署而已&#xff0c;没有FINETUNE、没有Langchain更没有外挂知识库&#xff0c;所以从申请资源——>开通虚机——>…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

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

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

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

向量几何的二元性:叉乘模长与内积投影的深层联系

在数学与物理的空间世界中&#xff0c;向量运算构成了理解几何结构的基石。叉乘&#xff08;外积&#xff09;与点积&#xff08;内积&#xff09;作为向量代数的两大支柱&#xff0c;表面上呈现出截然不同的几何意义与代数形式&#xff0c;却在深层次上揭示了向量间相互作用的…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...

【QT控件】显示类控件

目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏&#xff1a;QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...

Python异步编程:深入理解协程的原理与实践指南

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 持续学习&#xff0c;不断…...