TOP-K问题
目录
问题描述
解法及思想
第一种方式
算法思想
具体实现
第二种方式
算法思想
具体实现
问题描述
Top-K问题是一个十分经典的问题,一般有以下两种方式来描述问题:
- 在10亿的数字里,找出其中最大的100个数;
- 在一个包含n个整数的数组中,找出最大的100个数。
前边两种问题描述稍有区别,但都是说的Top-K问题,前一种描述方式是说这里也许没有足够的空间存储大量的数字或其他东西,我们最好可以在一边输入数据,一边求出结果,而不需要存储数据;后一种说法则表示可以存储数据,这种情况下,最简单直观的想法就是对数组进行排序,取后100个数即为所求。
解法及思想
第一种方式
这种情况下,关键在于不能消耗太大的内存,无法通过数组的简单排序来求取最大的K个数,于是我们应该想到堆排序,求最大的K个数,就采用大小为K的最小二叉堆来实现;我们知道二叉堆可以看作是一颗近似的完全二叉树,其根节点正好就是K个数中最小的一个。
算法思想
先输入K个数,建立一个大小为K的最小二叉堆,接着每输入一个数,与堆的根节点进行比较,如果比根节点还小,说明不可能为最大的K个数之一,如果比根节点大,那么替换根节点的值,接着下沉根节点,维护二叉堆的性质。这样到成功输入所有数据后,最小二叉堆里剩下的就为最大的K个数。(如果求最小的K个数,同理换成最大二叉堆即可)。
时间复杂度由于算法主要涉及对二叉堆结构的操作,所以总体时间复杂度为O(nlgK)
。
具体实现
/*
*代码采用STL中的最小优先队列实现,由于STL中自带最小优先队列,其底层就是二叉堆实现,
*所以就不再手写二叉堆了。最小优先队列顶层元素总是队列中最小的元素,也就是二叉堆堆顶。
*/#include <iostream>
#include <queue>
#include <vector>
using namespace std;/*由于STL自带优先队列是默认最大优先的,所以自己写了一个比较函数,将其改为最小优先*/
struct cmp1 {bool operator ()(int &a, int &b) {return a>b; //最小值优先}
};int main() {//这里用来测试,输入格式:先输入需要求的最大K个数中的K值,再依次输入数据流int K = 0;cin >> K;int tmp = 0;int i = 0;priority_queue<int,vector<int>,cmp1> minHeap; //建立最小优先队列while (cin >> tmp) { //循环输入数据流if (i < K) { //先建立一个K个大小的优先队列,也就是K大小的二叉堆minHeap.push(tmp);}else { //算法实现if (tmp <= minHeap.top())continue;else if (tmp > minHeap.top()) {minHeap.pop();minHeap.push(tmp);}}i++;}while (!minHeap.empty()) { //输出最大的K个数cout << minHeap.top() << endl;minHeap.pop();}return 0;
}
第二种方式
这种情况,由于可以操作存储数据的数组,所以我们采用排序的方式进行求解,但一般的排序时间复杂度也挺高,题目只求最大的K个数,不需要完全排序;于是我们想到可以借用快排思想来进行求解。
算法思想
我们知道,每运行一次Partition函数都会确定一个数m的最终位置,且小于m的数均在其左边,大于m的数都在其右边,所以我们的目的就是当数m的右边正好有K-1个数的时候停止算法,得到答案。每次运行Partition函数时,根据前边上述性质,若
- K<右边数组长度,那么要找的K个数一定在m右边,对m右边的数组运行Partition函数;
- K=右边数组长度+1,那么正好找到最大的K个数,为数m以及其右边数组,停止算法;
- 其他情况,最大的K个数不仅仅在m数右边数组中,对m左边数组运行Partition函数。
时间复杂度:与快排类似,Quick Select同样也是不稳定的算法,最坏情况下时间复杂度会达到O(n^2),但平均性能也与快排类似,时间复杂度一般可认为为O(n)。
具体实现
#include <iostream>
#include <vector>using namespace std;void swap(vector<int>&arr, int l, int r)//元素交换函数
{int temp = arr[l];arr[l] = arr[r];arr[r] = temp;
}int Partition(vector<int>&arr, int left, int right)
{int less = left - 1;//选准左边界int more = right;//右边界int temp = arr[right];//选定基准位置while (left < more){if (arr[left] < temp){swap(arr, ++less, left++);//当前元素小于基准元素,左边界内扩}else if (arr[left] > temp)//当前元素大于基准元素,右边界内扩,左边界不变{swap(arr, --more, left);}elseleft++;}swap(arr, more, right);//最后一个基准位置交换return left;//如果存在元素相等情况,返回相同元素两侧的边界索引
}int main() {cout << "请输入K: " << endl;int K = 0; //测试部分,输入需要求的K值大小,然后再依次输入数组元素cin >> K;int tmp = 0;vector<int> vec = {1,2,6,8,10,50,34,36,27,58,70,66};int size = vec.size();if (size == 0 || K > size)return 0;if (size == K){for (int i = 0; i < size; i++) { //测试部分,输出需要求的K个数cout << vec[i] << endl;}}int left = 0;int right = vec.size() - 1;int index = Partition(vec, left, right);while (index != size - K) { //当Partition返回值及右边部分不是K大小时,继续循环int sizeOfRight = size - index - 1; //记录index右边数组长度大小if (K <= sizeOfRight) {index = Partition(vec, index + 1, right);}else if (K == sizeOfRight + 1) //这一步好像有点多余,while循环保证了这点,但为了对应博客文字描述就加上了continue;else if (K > sizeOfRight + 1) {index = Partition(vec, left, index - 1);}}cout << "输出TOPK个元素: " << endl;for (int i = index; i < size; i++) { //测试部分,输出需要求的K个数cout << vec[i] << " ";}cout << endl;return 0;
}
相关文章:
TOP-K问题
目录 问题描述 解法及思想 第一种方式 算法思想 具体实现 第二种方式 算法思想 具体实现 问题描述 Top-K问题是一个十分经典的问题,一般有以下两种方式来描述问题: 在10亿的数字里,找出其中最大的100个数;在一个包含n个整…...

【保姆级从0到1】UE5 蓝图入门教程1:关卡、蓝图入门
20230113 1、新建项目 新建选择 UE 5.1 项目 选择蓝图,项目位置 改变编辑器布局,选择经典布局 2、关卡与蓝图 选择 File -> New Level 准备创建关卡 选择 Basic,点击 Create 进行创建 Ctrl S 保存新建的关卡 关卡蓝图的打开 鼠标右键&…...

【码银送书第六期】《ChatGPT原理与实战:大型语言模型的算法、技术和私有化》
写在前面 2022年11月30日,ChatGPT模型问世后,立刻在全球范围内掀起了轩然大波。无论AI从业者还是非从业者,都在热议ChatGPT极具冲击力的交互体验和惊人的生成内容。这使得广大群众重新认识到人工智能的潜力和价值。对于AI从业者来说…...
redis 报错 Redis protected-mode 配置文件没有真正启动
(error) DENIED Redis is running in protected mode because protected mode is enabled Redis protected-mode 是3.2 之后加入的新特性,在Redis.conf的注释中,我们可以了解到,他的具体作用和启用条件 链接redis 时只能通过本地localhost …...

解决a标签内容中img标签和p标签垂直方向间隔太大的问题
现象如下: 对应的html结构: 解决办法:给a标签设置:display: inline-block和line-height属性。 然后问题解决: 具体原理如下(由chatgpt回答): display: inline-block 可以减少垂直方…...

如何选择靠谱的全景平台?VR全景加盟从哪方面对比?
VR全景行业经过近几年的发展,已经逐渐普及开来,线下各个行业都有实体商家开始引入VR全景去做营销宣传推广了。不少老板也意识到线上线下双渠道的重要性,而VR全景的存在就刚好满足各行各业的需求,从这一点不难看出,VR全…...
CentOS系统环境搭建(十八)——CentOS7安装Docker20.10.12和docker compose v2
centos系统环境搭建专栏🔗点击跳转 CentOS7安装Docker20.10.12和docker compose v2 关于Docker旧版本和docker compose1.0版本的安装可以看这一篇CentOS系统环境搭建(三)——Centos7安装Docker&Docker Compose。 1.卸载旧版本 卸载do…...

NebulaGrap入门介绍和集群安装部署
长风破浪八千里,落日晚霞不回头。 ——大宁。 NebulaGrap——分布式图数据库 官方文档: NebulaGraph Database手册 官方文档 介绍 简介: NebulaGraph 一款开源、分布式图数据库,擅长处理超大规模数据集。 Nebula …...

thinkphp5.0 composer 安装oss提示php版本异常
场景复现: 本地 phpstudy 环境,安装的有7.0到7.3三个版本,首先确认composer已经安装 composer安装阿里云oss的命令为:composer require aliyuncs/oss-sdk-php 运行报错: Problem 1- Root composer.json requires php…...

AList dokcer安装及百度网盘挂载
AList是开源的网盘管理工具。本文介绍如何通过docker安装AList并挂载百度网盘 1、AList安装 1.1、系统安装 通过docker命令进行安装,命令如下: docker run -d --restartalways -v /etc/alist:/opt/alist/data -p 5244:5244 --name"alist" xhofe/alist:…...
whereIn 遇到了最大限制,临时表处理方式
当使用whereIn 遇到了限制,比如whereIn target ID 已经超过了10万级别,但是又没办法join其他库表时,可以使用临时表的方式解决,临时表是以一种会话的方式存在,意味着你断开了mysql 这个临时会话会自动销毁。 为了创建…...

基于SSM的校园快递代取系统设计与实现
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用JSP技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…...

MySQL事务详细讲解
文章目录 什么是事务:1.事务有哪些特性2.并发事务会引起什么问题3.事务的隔离级别有哪些4.Read View在MVCC中如何工作Read View 有四个重要的字段使用 InnoDB 存储引擎的数据库表,它的聚簇索引记录中都包含下面两个隐藏列: 5.可重复读是怎么工作的6.读提…...
[linux] mmcv-full 安装的时候 Building wheel 卡住
(已解决)FileNotFoundError: [Errno 2] No such file or directory: ‘:/usr/local/cuda-11.8/bin/nvcc‘_鳗小鱼的博客-CSDN博客 安装mmcv一直卡在建车轮_梦想成为大佬的王老八的博客-CSDN博客 pip install -U openmim mim install mmcv...

Python怎么实现更高效的数据结构和算法? - 易智编译EaseEditing
要实现更高效的数据结构和算法,你可以考虑以下几个方面的优化: 选择合适的数据结构: 选择最适合你问题的数据结构至关重要。例如,如果需要频繁插入和删除操作,可能链表比数组更合适。如果需要高效查找操作࿰…...
03-zookeeper节点动态上下线案例
服务器动态上下线监听案例 需求 在分布式系统中,主节点可以有多台,可以动态上下线,任意一台客户端都能实时感知到主节点服务器的上下线。 需求分析 客户端能实时洞察到服务器上下线的变化 基本流程: 1.服务端启动时去注册…...
如何使用TensorFlow完成线性回归
线性回归是一种简单的预测模型,它试图通过线性关系来预测目标变量。在TensorFlow中,我们可以使用tf.GradientTape来跟踪我们的模型参数的梯度,然后用这个信息来优化我们的模型参数。 以下是一个简单的线性回归的例子: pythonimpo…...

@controller和@RestController的区别
//controller和RestController的区别:RestController的返回值就是结果被输出在浏览器 //controller的返回值会到resources的templates下找 返回值".html" 页面 1.controller 简单的来说,当我们的返回值需要跳转大另一个页面时候,我们就会使…...

GeoNet: Unsupervised Learning of Dense Depth, Optical Flow and Camera Pose 论文阅读
论文信息 题目:GeoNet: Unsupervised Learning of Dense Depth, Optical Flow and Camera Pose 作者:Zhichao Yin and Jianping Shi 来源:CVPR 时间:2018 Abstract 我们提出了 GeoNet,这是一种联合无监督学习框架&a…...

蓝桥杯官网填空题(振兴中华)
题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小明参加了学校的趣味运动会,其中的一个项目是:跳格子。 地上画着一些格子,每个格子里写一个字,如下所示࿱…...

铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...