786. 第k个数
2024-09-06 00:24:57
一、理解感悟
1、这是快速排序模板的练习题。
2、不一样的地方在于它可以利用快排模板,但却不需要真的把所有数据排序完成,每次一分为二后,只关心自己所有的那一半,就是可以节约一半的递归。
3、由于是关心“位置”(第几个),所以需要携带这个参数。
4、位置这个参数不是一成不变的,因为如果在左侧,那么就是原来的位置,如果在右侧,那就需要减去整个左侧的长度。
二、C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
/**
* 功能:利用快速排序对数组进行排序
* 关键词:小哨兵,分治(递归)
* @param q 要排序的数组,注意:函数中数组参数是按地址传递的,
* 就是能把原来的数组修改掉,不是抄出来一份给函数处理的
* @param l 左起的下标位置
* @param r 右末的下标位置
*/
void quick_sort(int q[], int l, int r, int k) {
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j)swap(q[i], q[j]);
}
//这里可以对原模板做出了一些优化,划分边界时,目标位置是在左还是在右,
//在哪边就继续排序哪些,另一个就不需要排序了,可以加快运算速度。
int p = j - l + 1;//左侧长度
if (k <= p) quick_sort(q, l, j, k);//在左侧排左侧
else quick_sort(q, j + 1, r, k - p);//在右侧排右侧,但要注意位置值要有变化,要把左侧长度减去
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> q[i];
//调用快排模板
quick_sort(q, 1, n, k);
//输出结果
printf("%d", q[k]);
return 0;
}
最新文章
- json中含有Unicode的处理办法 C#
- Java程序生成exe可执行文件详细教程(图文说明)
- python实验一:画图
- Mysql学习笔记(八)索引
- php时间函数
- MTD NANDFLASH驱动相关知识介绍
- ViewPager的用法实例
- Vijos1352 NOI2006 最大获利 最小权闭合图
- IE JavaScript字符串转换成Date后出现NaN错误
- linux ar 命令的使用
- hdu 3333 Turing Tree
- iot 表主键存放所有数据,且按数据插入顺序排序
- 9.TCP:传输控制协议
- servlet前台中文参数处理
- 201521123101 《Java程序设计》第7周学习总结
- 初学PHP心得(第一天)
- webrtc视频数据render流程
- PHPUnit-附录 B. 标注
- 最近用spring4.x整合Jackson------>;java.lang.ClassNotFoundException:
- Python学习——1