1.洛谷题P1923 求第k小的数
题目描述
输入 n（1≤n<5000000 且 n 为奇数）个数字ai（1≤ai<109），输出这些数字的第 k 小的数。最小的数是第 0 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
输入格式
无
输出格式
无
输入输出样例
输入 ：
5 1
4 3 2 1 5输出 ：
2题目解析：
这道题一开始以为是很简单的sort直接乱杀，没想到写出来… 就对了60%的样例
第一版代码如下：
#include<bits/stdc++.h>
using namespace std;
const long long N=5e7+1;
int q[N];
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>q[i];
}
sort(q,q+n);
cout<<q[k]<<" ";
return 0;
} 测试样例结果如下：
发现有些样例仍然不能通过显示超时了，因此我们在算法上对它进行优化一下，改变了一下这个排序算法和搜索第k个数的算法
第二版代码如下：（这次可以AC啦！！！）
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
void qsort(int l,int r)
{
int i=l,j=r,mid=x[(l+r)/2];
do
{
while(x[j]>mid)
j--;
while(x[i]<mid)
i++;
if(i<=j)
{
swap(x[i],x[j]);
i++;
j--;
}
}
while(i<=j);
//快排后数组被划分为三块： l<=j<=i<=r
if(k<=j) qsort(l,j);//在左区间只需要搜左区间
else if(i<=k) qsort(i,r);//在右区间只需要搜右区间
else //如果在中间区间直接输出
{
printf("%d",x[j+1]);
exit(0);
}
}
int main()
{
int n;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&x[i]);
qsort(0,n-1);
}测试样例结果如下：
这次可以通过啦！
但是我发现题目中提到了一个
nth_element没见过，于是我又去了解了一下nth_element的用法和写法，所以有了第三版代码😘
第三版代码：(O(n))
在 STL 里有一个神奇的函数 nth_element。
它的用法是 nth_element(a+x,a+x+y,a+x+len)。
执行之后数组 a 下标 x 到x+y-1 的元素都小于 a[x+y]，下标 x+y+1 到 x+len−1 的元素 都大于 a[x+y]，但不保证数组有序。此时 a[x+y] 就是数组区间 x 到 x+len−1 中第 y 小的数，当然也可以自己定义 cmp 函数。
nth_element 的时间复杂度是O(n) 的，不过 STL 常数普遍较大……但还是能过此题。
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{
int n;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&x[i]);
nth_element(x,x+k,x+n);//简短又高效
printf("%d",x[k]);
}
