有没有做策划案例的网站,企业合作的响应式网站,wordpress上传数据,惠阳做网站公司做道简单一点的题巩固一下
基本思路
与上一个整体相似#xff0c;通过快速排序将长度为n的整数数列变为从小到大的有序数组#xff0c;在拿出其中第k个数。
题目描述 给定一个长度为 n 的整数数列#xff0c;以及一个整数 k#xff0c;请用快速选择算法求出数列从小到大…做道简单一点的题巩固一下
基本思路
与上一个整体相似通过快速排序将长度为n的整数数列变为从小到大的有序数组在拿出其中第k个数。
题目描述 给定一个长度为 n 的整数数列以及一个整数 k请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式 输入共两行。 第一行包含整数 n和k。 第二行包含 n 个整数所有整数均在 1∼1e9 范围内表示整个数列。
输出格式 输出一个整数表示数列的第 k 小数。
数据范围 1≤n≤100000 1≤k≤n
输入样例 5 3 3 1 2 4 5
输出样例 3
具体实现
1. 模板 实现思路 我们假设小于分界点的个数为sl大于分界点的个数为sr。
此时整体便会分为两种情况
当k≤sl时第k小的数一定在分界点的左边此时只需要对左边进行递归排序第k小的数在sl上仍为第k个数。 当k≥sl时第k小的数一定在分界点的右边此时只需要对右边进行递归排序第k小的数在sr上变为第 k-sl 个数。代码注解 在C当中如果局部变量和全局变量重名时会优先使用局部变量因此可以重名。
因为 1≤k≤n 所以如果 l≥r 的话就说明整个数列当中只有一个数此时这个数便是我们的答案因此返回 q[l]q[r] 均可。
从 l 到 j 一共有 j-l1 个数此时让k与其进行比较决定我们应该对哪部分区间进行递归处理具体可见上面实现思路。
实现代码
#include bits/stdc.h
using namespace std;const int N100010;
int n,k;
int q[N];
int quick_sort(int q[],int l,int r,int k)
{if(lr){return q[l];}int xq[lr1],il-1,jr1;while(ij){do{i;}while(q[i]x);do{j--;}while(q[j]x);if(ij){swap(q[i],q[j]);}}if(j-l1k){return quick_sort(q,l,j,k); }else{return quick_sort(q,j1,r,k-(j-l1));}
}
int main()
{cinnk;for(int i0;in;i){cinq[i];}coutquick_sort(q,0,n-1,k)endl;system(pause);return 0;
}2. STL
代码注解
STL大法好这里只需注意我从 i0 开始的因此第k个数对应在数组当中对应的应为第 k-1 个数。
实现代码
#include bits/stdc.h
using namespace std;const int N100010;
int n,k;
int q[N];
int main()
{cinnk;for(int i0;in;i){cinq[i];}sort(q,qn);coutq[k-1]endl;system(pause);return 0;
}
