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

786. 第k个数

文章目录

  • Question
  • Ideas
  • Code

Question

给定一个长度为 n
的整数数列,以及一个整数 k
,请用快速选择算法求出数列从小到大排序后的第 k
个数。

输入格式
第一行包含两个整数 n
和 k

第二行包含 n
个整数(所有整数均在 1∼109
范围内),表示整数数列。

输出格式
输出一个整数,表示数列的第 k
小数。

数据范围
1≤n≤100000
,
1≤k≤n
输入样例:
5 3
2 4 1 5 3
输出样例:
3

Ideas

Code

// 快排步骤(O(nlgn)):
// 1.寻找分界点x,a[l + r >> 1]
// 2.划分区间,使得左边均<=x,右边均>=x
// 3.递归左右两边
// 快速搜索步骤(O(n))
// 当进行到第2步时,左区间严格<=右区间,所以第k小的数要么在左区间,要么在右区间,
// 只需要递归一边即可,这由k与左区间的元素个数有关#include <iostream>using namespace std;const int N = 1E5 + 10;
int a[N];int quick_choose(int *a, const int& l, const int& r, const int& k)
{if (l >= r) return a[l];int x = a[l + r >> 1];int i = l - 1, j = r + 1;while(i < j){do i ++; while(a[i] < x); // 快排左边寻找a[i] >= xdo j --; while(a[j] > x);if (i < j) swap(a[i], a[j]);}int sl = j - l + 1;if (k <= sl) return quick_choose(a, l, j, k); // 左边区间的数目else return quick_choose(a,j + 1, r, k - sl);
}
int main()
{int n, k;scanf("%d%d", &n, &k);for (int i = 0; i < n; i ++) scanf("%d", &a[i]);cout << quick_choose(a, 0, n - 1, k) << endl;return 0;
}

相关文章:

786. 第k个数

文章目录 QuestionIdeasCode Question 给定一个长度为 n 的整数数列&#xff0c;以及一个整数 k &#xff0c;请用快速选择算法求出数列从小到大排序后的第 k 个数。 输入格式 第一行包含两个整数 n 和 k 。 第二行包含 n 个整数&#xff08;所有整数均在 1∼109 范围内&…...

用友-NC-Cloud远程代码执行漏洞[2023-HW]

用友-NC-Cloud远程代码执行漏洞[2023-HW] 一、漏洞介绍二、资产搜索三、漏洞复现PoC小龙POC检测脚本: 四、修复建议 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#…...

Transformer(二)(VIT,TNT)(基于视觉CV)

目录 1.视觉中的Attention 2.VIT框架&#xff08;图像分类&#xff0c;不需要decoder&#xff09; 2.1整体框架 2.2.CNN和Transformer遇到的问题 2.3.1CNN 2.3.2Transformer 2.3.3二者对比 2.4.公式理解 3TNT 参考文献 1.视觉中的Attention 对于人类而言看到一幅图可以立…...

Scratch 详解 之 线性→代数之——求两线段交点坐标

可能有人要问&#xff1a;求交点坐标有什么用呢&#xff1f;而且为啥要用线代来求&#xff1f;直线方程不行吗&#xff1f;&#xff1f;&#xff1f; 这个问题&#xff0c;我只能说&#xff0c;直线方程计算的次数过多了&#xff0c;而且动不动就要考虑线的方向&#xff0c;90的…...

Python-组合数据类型

今天要介绍的是Python的组合数据类型 整理不易&#xff0c;希望得到大家的支持&#xff0c;欢迎各位读者评论点赞收藏 感谢&#xff01; 目录 知识点知识导图1、组合数据类型的基本概念1.1 组合数据类型1.2 集合类型概述1.3 序列类型概述1.4 映射类型概述 2、列表类型2.1 列表的…...

vue3+vue-simple-uploader实现大文件上传

vue-simple-uploader本身是基于vue2实现,如果要使用vue3会报错。如何在vue3中使用,可参考我的另一篇文章:解决vue3中不能使用vue-simple-uploader__Jyann_的博客-CSDN博客 一.实现思路 使用vue-simple-uploader组件的uploader组件,设置自动上传为false,即可开启手动上传。…...

自适应变异麻雀搜索算法及其Matlab实现

麻雀搜索算法( sparrow search algorithm&#xff0c;SSA) 是2020 年新提出的一种元启发式算法[1]&#xff0c;它是受麻雀种群的觅食和反捕食行为启发&#xff0c;将搜索群体分为发现者、加入者和侦察者 3 部分&#xff0c;其相互分工寻找最优值&#xff0c;通过 19 个标准测试…...

ETL技术入门之ETLCloud初认识

首先ETL是什么&#xff1f; ETL代表“Extract, Transform, Load”&#xff0c;是一种用于数据集成和转换的过程。它在数据管理和分析中扮演着重要的角色。下面我们将分解每个步骤&#xff1a; Extract&#xff08;抽取&#xff09;&#xff1a; 这一步骤涉及从多个不同的数据源…...

uniapp项目如何运行在微信小程序模拟器上

在HbuilderX中的小程序写完后自己一定要保存&#xff0c;否则会出不来效果 那么怎么让uniapp项目运行在微信小程序开发工具中呢 1 在hbuilderx中点击运行到小程序模拟器 2 然后在项目目录中会生成一个文件夹 在微信小程序开发软件中的工具>安全设置>打开端口 或者在微…...

数据挖掘全流程解析

数据挖掘全流程解析 数据指标选择 在这一阶段&#xff0c;使用直方图和柱状图的方式对数据进行分析&#xff0c;观察什么数据属性对于因变量会产生更加明显的结果。 如何绘制直方图和条形统计图 数据清洗 观察数据是否存在数据缺失或者离群点的情况。 数据异常的两种情况…...

详细介绍如何对音乐信息进行检索和音频节拍跟踪

在本文中,我们将了解节拍的概念,以及我们在尝试跟踪节拍时面临的挑战。然后我们将介绍解决问题的方法以及业界最先进的解决方案。 介绍 音乐就在我们身边。每当我们听到任何与我们的心灵和思想相关的音乐时,我们就会迷失其中。我们下意识地随着听到的节拍而敲击。您一定已…...

Java课题笔记~ HTTP协议(请求和响应)

Servlet最主要的作用就是处理客户端请求&#xff0c;并向客户端做出响应。为此&#xff0c;针对Servlet的每次请求&#xff0c;Web服务器在调用service()方法之前&#xff0c;都会创建两个对象 分别是HttpServletRequest和HttpServletResponse。 其中HttpServletRequest用于封…...

在x86下运行的Ubuntu系统上部署QEMU用于模拟RISC-V硬件环境

1.配置工作环境 sudo apt install gcc bison flex libncurses-dev ninja-build \pkg-config build-essential zlib1g-dev pkg-config libglib2.0-dev \binutils-dev libboost-all-dev autoconf libtool libssl-dev \libpixman-1-dev python-capstone virtualenv software-prop…...

网络爬虫选择代理IP的标准

Hey&#xff0c;小伙伴们&#xff01;作为一家http代理产品供应商&#xff0c;我知道网络爬虫在选择代理IP时可能会遇到些问题&#xff0c;毕竟市面上有很多选择。别担心&#xff01;今天我要给大家分享一些实用的建议&#xff0c;帮助你们选择适合网络爬虫的代理IP。一起来看看…...

RxJava 复刻简版之三,map 多次中转数据

案例代码&#xff1a;https://gitee.com/bobidali/lite-rx-java/commit/292e9227a5491f7ec6a07f395292ef8e6ff69290 RxJava 的调用第一步是封装了观察者接受了数据的处理&#xff0c;进一步就是使用 map 将数据操作传递给上下游 1、类似Observer.create 创建一个简单的观察者…...

06 Word2Vec模型(第一个专门做词向量的模型,CBOW和Skip-gram)

博客配套视频链接: https://space.bilibili.com/383551518?spm_id_from=333.1007.0.0 b 站直接看 配套 github 链接:https://github.com/nickchen121/Pre-training-language-model 配套博客链接:https://www.cnblogs.com/nickchen121/p/15105048.html 神经网络语言模型(NNL…...

Axure RP9小白安装教程

第一步&#xff1a; 打开&#xff1a;Axure中文学习网 第二步&#xff1a; 鼠标移动软件下载&#xff0c;点击Axure RP 9下载既可 第三步&#xff1a; 注意&#xff1a;Axure RP 9 MAC正式版为苹果版本&#xff0c;Axure RP 9 WIN正式版为Windows版本 中文汉化包&#xff…...

腾讯云CVM服务器2核2g1m带宽支持多少人访问?

腾讯云2核2g1m的服务器支持多少人同时访问&#xff1f;2核2g1m云服务器短板是在1M公网带宽上&#xff0c;腾讯云服务器网以网站应用为例&#xff0c;当大规模用户同时访问网站时&#xff0c;很大概率会卡在公网带宽上&#xff0c;所以压根就谈不上2核2G的CPU内存计算性能是否够…...

8.12学习笔记

在PyTorch中&#xff0c;Dataset和DataLoader是用于处理数据的两个重要类。Dataset类是一个抽象类&#xff0c;用于表示数据集。它的主要作用是将数据加载到内存中&#xff0c;并提供一种统一的方式来访问数据。为了使用Dataset类&#xff0c;你需要继承它并实现两个方法&#…...

计算机体系中的不同的缓存存储层级说明

分级说明 L1缓存的标准延迟是4个周期。这意味着&#xff0c;当CPU请求数据时&#xff0c;L1缓存需要4个时钟周期来将数据传输给CPU。 L2缓存的标准延迟是12个周期。相对于L1缓存&#xff0c;L2缓存的容量更大&#xff0c;但其读取速度更慢&#xff0c;需要更多的时钟周期来传输…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

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

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...