题目描述

这道题当时卡了我很久的是k的变化，

感觉在递归后半部分时k不用减去sl也可以(错误的)
k必须减sl，我们指定的第k个数在递归的部分中不再是第k个了(正确)

样例

8 6
1 9 2 8 3 7 4 5

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>

using namespace std;
const int N=100010;
int a[N];
int n,k;
int quick_choose(int l,int r,int k)//l，r是区间左右端点，k是第k小数 
{

    if(l==r) return a[l];

    int x=a[l],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }

    int sl=j-l+1;
    if(k<=sl)return quick_choose(l,j,k);
    else if(k>sl)
    return quick_choose(j+1,r,k-sl);
}
int main()
{
    cin>>n>>k;

    for(int i=0;i<n;i++)cin>>a[i];

    cout<<quick_choose(0,n - 1,k)<<endl;

    return 0;
}