C++的STL库中的nth_element()方法,默认是求区间第k小的(划重点)。
举个栗子求第3小,对于 a[9]={4,10,6,9,1,8,2,3,7};
nth_element(a,a+2,a+9),将下标为2,也就是第3个数放在正确的位置,求的是第3小的数a[2]。(下标从零开始)
nth_element(a,a+k,a+n),函数只是把下标为k的元素放在了正确位置,对其它元素并没有排序,当然k左边元素都小于等于它,右边元素都大于等于它,所以可以利用这个函数快速定位某个元素。
分析
使用STL中的nth_element()进行求解,非常方便。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],n,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
nth_element(a,a+k-1,a+n); //下标从0开始,也就是k-1,表示第k个数
printf("%d",a[k-1]);
return 0;
}