快速选择

简介: 题目:给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个 数。输入格式第一行包含两个整数 n 和 k。第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整数数列。输出格式输出一个整数,表示数列的第 k 小数。数据范围1≤n≤100000,1≤k≤n输入样例:5 32 4 1 5 3输出样例:3

题目:

给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个 
数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第 k 小数。
数据范围
1≤n≤100000,
1≤k≤n
输入样例:
5 3
2 4 1 5 3
输出样例:
3

分析:

同样的道理,用sort函数排完序之后输出第k个数,时间复杂度较高,也可以快速排序完之后输出第k个数,这两个复杂度都比较高,快速选择算法时间复杂度为O(n)。

源码:

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=100010;
int a[N],n,k; 
int  quick_sort(int l,int r,int k)
{
if(l==r) return a[l];
int i=l-1,j=r+1,x=a[(i+j)/2];
while(i<j)
{
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j) swap(a[i],a[j]);
}
int sl=j-l+1;
if(k<=sl)return quick_sort(l,j,k);
return quick_sort(j+1,r,k-sl);
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)  scanf("%d",&a[i]);
cout<<quick_sort(0,n-1,k)<<endl;
return 0;
}


目录
相关文章
|
存储 自然语言处理 前端开发
领域驱动设计(DDD)-基础思想
一、序言     领域驱动设计是一种解决业务复杂性的设计思想,不是一种标准规则的解决方法。在领域驱动设计理念上,各路大侠的观点也是各有不同,能力有限、欢迎留言讨论。 二、领域驱动设计 DDD是什么 wiki释义:     领域驱动设计(英语:Domain-driven design,缩写 DDD)是一种通过将实现连接到持续进化的模型[1]来满足复杂
7779 0
|
7月前
|
API
咨询关于大模型的API接口,多用户调用的问题
是不是说一个API_key,只一个时间问一个问题?
225 1
|
2月前
|
存储 安全 算法
RAW格式硬盘打不开?这样做让它恢复如初
当硬盘或U盘突然显示为RAW格式,无法打开并提示“需格式化”时,切勿立即格式化或运行chkdsk,这可能导致数据永久丢失。RAW格式是系统无法识别文件系统的状态,常见原因包括分区损坏、病毒、坏道或异常关机。正确做法是先用专业工具恢复数据,通过智能加载或深度扫描找回文件。数据恢复后,再对硬盘进行格式化修复。本文详解操作步骤与注意事项,助你安全恢复数据、修复磁盘。
|
4月前
|
机器学习/深度学习 自然语言处理 数据可视化
⼤模型驱动的DeepInsight Copilot在蚂蚁的技术实践
本文整理自潘兰天(蚂蚁数据智能团队数据分析平台技术专家)在DA数智大会2025·上海站的演讲实录。
|
9月前
|
Web App开发 IDE JavaScript
Selenium IDE:Web自动化测试的得力助手
Selenium IDE是开源的Web自动化测试工具,适用于Chrome、Firefox等多款浏览器。它提供简单的录制与回放功能,用户可通过录制浏览器操作自动生成测试脚本,支持导出为多种编程语言,便于非专业测试人员快速上手,有效提升测试效率与质量。
842 6
Selenium IDE:Web自动化测试的得力助手
|
开发框架 前端开发 JavaScript
网页CAD中二维CAD图转三维CAD的方法
本文介绍了一种将网页CAD中的二维图纸转换成三维模型的方法,特别聚焦于通过拉伸平面图形至一定高度来实现三维效果。文中利用了mxcad和mxcad3d两个框架,前者负责读取和解析二维CAD图纸,后者则基于这些数据构建三维模型。文章详细阐述了安装配置步骤及代码实现细节,包括创建项目、安装依赖、编写HTML与JavaScript代码等,并提供了完整的示例代码。最终实现了从二维图纸自动转换并展示三维模型的功能,同时添加了交互元素以方便用户操作。
网页CAD中二维CAD图转三维CAD的方法
|
10月前
|
缓存 C# 开发者
C# 一分钟浅谈:Blazor Server 端开发
本文介绍了 Blazor Server,一种基于 .NET 的 Web 开发模型,允许使用 C# 和 Razor 语法构建交互式 Web 应用。文章从基础概念、创建应用、常见问题及解决方案、易错点及避免方法等方面详细讲解,帮助开发者快速上手并提高开发效率。
244 2
|
图形学
【制作100个unity游戏之26】unity2d横版卷轴动作类游戏1(附带项目源码)
【制作100个unity游戏之26】unity2d横版卷轴动作类游戏1(附带项目源码)
282 0
|
前端开发
什么是精灵图?
什么是精灵图?
337 0
|
监控 安全 Cloud Native
【重磅干货】如何构建 API 生态促进企业上下游合作
【重磅干货】如何构建 API 生态促进企业上下游合作
【重磅干货】如何构建 API 生态促进企业上下游合作