首页 > 其他分享 >2022-11-01每日一题

2022-11-01每日一题

时间:2022-11-01 19:13:47浏览次数:105  
标签:11 sort 01 数列 输出 int 整数 2022 quick

第k个数

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

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

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

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

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


个人解析:
明显的模板题,快排之后输出第k个数,那就来复习一下快速排序的知识!
主要思想是分而治之
算法就是:

  1. 在[l,r]中随机选一个数作为基准点,将整个数组分成两个子数组。
  2. 让这个数的左边的数都比他小,右边的数都比他大。(如果是要降序就相反)
  3. 递归排序左右两个子数组。

#include<bits/stdc++.h>
const int N = 100010;
int a[N];

void quick_sort(int l,int r){
	if(l <= r) return ;
	int x = a[ (l+r) >> 1], i = l - 1, j = r + 1;
	while(i<j){ // 快排的重点
		do i++ while(a[i] > x);
		do j-- while(a[j] < x);
		if(i < j) swap(i,j);	
	// 找到从左边第一个比x大的,右边第一个比x小的,如果符合范围就交换这两个出错的
	}
	quick_sort(l,j),quick_sort(j+1,r); 
	// 退出循环一定是i=j,此时i(j)左边的数一定都比他小,右边的数一定都比他大
}


int main(void){
	int n,k;
	cin >> n >> k;
	for(int i=0; i < n ; ++i)   scanf("%d",&a[i]);
    quick_sort(a,0,n-1);
    printf("%d",a[k-1]);
	return 0;
}

标签:11,sort,01,数列,输出,int,整数,2022,quick
From: https://www.cnblogs.com/WangChe/p/16848822.html

相关文章

  • Win11 使用Hyper-V快速安装Win10
    由于我的电脑更新成了win11,很多东西还不如win10找了半天没有找到hyper-v,于是就搜索记录一下过程过程安装hyper-v打开新建一个Hyper-V.cmd文件,将下面的内容粘入保存。......
  • Codeforces Round #113 (Div. 2) E. Tetrahedron(dp/递推)
    https://codeforces.com/problemset/problem/166/E题目大意:给定一个正三角锥,最上面的顶点是D点,下面三个点分别标号为ABC给定n次,我们初始化在D点上,并且要求最后第n步也......
  • 22.11.1(学习tensorflow模型结构)
    1、.h5文件包括两种,没有有网络结构用model.load_weights本来训练的模型测试集和验证集效果都很好,但是预测的时候效果特别差,而且每次效果都不一样,我就觉得我训练的参数模......
  • CSP2022 游记
    Day-1,-2,-3...每天模拟赛都被吊打,心情烦躁。Day0高强度打摆训练,考前打摆加\(\text{RP}\)。Day1上午睡到\(12\)点,没有考\(\text{J}\)组。下午考场在自己学校......
  • 【408】2014
    t45每个cache块由标记项、数据区组成!!访问A[0],查TLB未命中,查页表未命中,因此去磁盘调数据(OS有相应的机制去找到页面与磁盘地址的对应关系)调入主存中(同时更新页表和TLB(一般......
  • 11Jmeter之优化jenkins上html报告格式
    问题:当在jenkins上查看HTML报告时,发现报告格式不美观!  解决一:临时解决方法1、进入Manage Jenkins->Scriptconsole,输入如下命令并进行执行。System.setPropert......
  • 深度学习从入门到精通——VOC 2012数据读取(pytorch)
    fromtorch.utils.dataimportDatasetimportosimporttorchimportjsonfromPILimportImagefromlxmlimportetreeclassVOC2012DataSet(Dataset):"""读取解析PASC......
  • 洛谷 P3183 [HAOI2016]食物链(dfs+记忆化搜索)
    https://www.luogu.com.cn/problem/P3183题目大意:给定n个节点,标号分别为1——n,然后给出m条有向边,问我们不同的食物链路径有多少?输入#1101612141102325......
  • 【一句日历】2022年11月
    【2022年11月1日·星期二】若深情不能对等,我愿爱得更多的是我。                                 ......
  • 0xgame2022 PWN week1-4
    0xgameweek1pwn1签到的nc,catflagpwn2ret2backdoor,一个栈溢出#encoding=utf-8frompwnimport*importosimportsysimporttime#fromae64importAE64#fro......