1.题目
【深基9.例4】求第 k 小的数
题目描述
输入 \(n\)（\(1 \le n < 5000000\) 且 \(n\) 为奇数）个数字 \(a_i\)（\(1 \le a_i < {10}^9\)），输出这些数字的第 \(k\) 小的数。最小的数是第 \(0\) 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
输入格式
输出格式
样例 #1
样例输入 #1
5 1
4 3 2 1 5
样例输出 #1
2
2.题解
2.1 分治算法
0.注意
这里我一直有两个测试点过不去，经过资料查阅之后得知：cin，cout的读入输出效率过慢，因为他们有着缓冲机制和一些其他安全措施，但是这里读入的数1≤n<5000000过多
这里可以选择使用scanf和printf，或者像我这里使用快读的方法
这里的inline是内联函数的意思，直接将函数复制到相应位置，而不是调用函数，通过栈保存上下文信息，对于频繁使用的函数提高了效率
1.思路
这里最终l和r的位置有两种情况：
只要注意l的位置是右区间的边界，而r的位置是左区间的边界即可。
而若是有 k >= l,说明k的值在右区间内，若是k==l不就是arr[l]呢？因为右区间内的数并不是顺序排列，无法判断是否就是第k大的数
如果 k <= r同理；
还有一种可能就是l和r位置的第二种情况，k在他们之间，这时候实际上就是找到了需要的那个数，这里可以像我这里继续递归，然后通过返回条件返回该值，也可以直接输出该值。
2.代码
#include<bits/stdc++.h>
using namespace std;
int k, ans;
//这里arr必须设置为全局变量，不然每次都作为函数输入参数，会消耗大量资源和时间爱你
vector<int> arr;
void swap(int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 这里由于cin读入过慢，而这里n（ 1≤n<5000000且n为奇数），所以使用快读缩短读取时间爱
inline int read(){ //快读
char ch=getchar();
int x=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
void sortNum(int begin, int end){
if(begin == end){
ans = arr[begin];
return;
}
int l = begin, r = end;
int currNum = arr[(end - begin) / 2 + begin];
while(l <= r){
//由于我取的currNum是中位数，所以l第一次最多停留在中位数，r同理
//由于后面if中的交换，l指向的必是小于等于currNum的值，r指向的必是大于等于currNum的值
//后续的几次while循环，必不可能在while循环中出现 l > r的情况，最多是 l = r;
while(arr[l] < currNum) l++; //l指向第一个不小于currNum的值
while(arr[r] > currNum) r--; //r指向第一个不大于currNum的值
if(l <= r){
swap(l, r);
l++;
r--;
}
}
// 结束后l和r有两种情况：1. r+1 = l; 2. r+1 = l - 1;
// l指向的是右区间边界， r指向的是左区间边界
if(k >= l) sortNum(l, end); // 表明在右区间
else if(k <= r) sortNum(begin, r); //表明在左区间
//除去上面两种，这里只有一种情况：r + 1 = k = l - 1;
else {
sortNum(r+1 , l-1);
}
}
int main(){
int n;
n = read();
k = read();
arr.resize(n);
for(int i = 0; i < n; i++){
arr[i] = read();
}
sortNum(0, n - 1);
cout << ans;
return 0;
}
2.2 nth_element函数
思路
在强大的STL库中存在一个神奇的函数，那就是nth_element，这个函数主要用来将数组元素中第k小的整数排出来并在数组中就位，随时调用，可谓十分实用。
函数语句：nth_element(数组名,数组名+第k小元素,数组名+元素个数)
代码
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[5000010];
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
nth_element(a,a+k,a+n);//使第k小整数就位
printf("%d",a[k]);//调用第k小整数
}