当前位置:网站首页>【acwing】786. 第k个数
【acwing】786. 第k个数
2022-07-07 07:46:00 【percation】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n,k;
int qs(int l, int r, int k){
if(l == r) return q[l];
int i = l - 1, j = r + 1, x = q[(l + r)/2];
while(i < j){
while(q[++i] < x) ;//实现左区间向右边前进,右区间向左边前进
while(q[--j] > x) ;
if(i < j) swap(q[i],q[j]);
}
int s1 = j - l + 1;//找到当时分界点在区间的位置,因区间从0开始,所以要加1
if(k <= s1)//当所要查询的数,在当前分界点的左边时,则进行左递归,否则进行右递归。
return qs(l, j, k);
return qs(j + 1,r, k - s1);
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 0; i < N; i++){
scanf("%d",&q[i]);
}
cout << qs(0,n-1,k) << endl;
return 0;
}
边栏推荐
- Performance optimization record of the company's product "yunzhujia"
- Basic chapter: take you through notes
- ORM--逻辑关系与&或;排序操作,更新记录操作,删除记录操作
- LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
- ORM -- query type, association query
- arcgis操作:dwg数据转为shp数据
- There is a problem using Chinese characters in SQL. Who has encountered it? Such as value & lt; & gt;` None`
- ORM -- grouping query, aggregation query, query set queryset object properties
- In addition to the objective reasons for overtime, what else is worth thinking about?
- ES6中的原型对象
猜你喜欢
Applet sliding, clicking and switching simple UI
Future development blueprint of agriculture and animal husbandry -- vertical agriculture + artificial meat
Delete a record in the table in pl/sql by mistake, and the recovery method
虚数j的物理意义
嵌入式背景知识-芯片
LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
Postman interface test I
LeetCode 练习——113. 路径总和 II
A wave of open source notebooks is coming
高数_第1章空间解析几何与向量代数_向量的数量积
随机推荐
phpcms实现PC网站接入微信Native支付
一文讲解单片机、ARM、MUC、DSP、FPGA、嵌入式错综复杂的关系
ORM--查询类型,关联查询
Methods of adding centerlines and centerlines in SolidWorks drawings
Qualifying 3
Bean 作⽤域和⽣命周期
In addition to the objective reasons for overtime, what else is worth thinking about?
Web3.0 series distributed storage IPFs
柏拉图和他的三个弟子的故事:如何寻找幸福?如何寻找理想伴侣?
Please ask me a question. I started a synchronization task with SQL client. From Mysql to ADB, the historical data has been synchronized normally
The applet realizes multi-level page switching back and forth, and supports sliding and clicking operations
Win10安装VS2015
IPv4套接字地址结构
Some test points about coupon test
Finally, there is no need to change a line of code! Shardingsphere native driver comes out
Weekly recommended short videos: what are the functions of L2 that we often use in daily life?
request对象对请求体,请求头参数的解析
运用tensorflow中的keras搭建卷积神经网络
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
Download Text, pictures and ab packages used by unitywebrequest Foundation