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…...

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

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...

人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...