4WA1AC,求助

P1923 【深基9.例4】求第 k 小的数

Li_wenjie @ 2021-09-02 20:12:33

#include<bits/stdc++.h>
using namespace std;
int a[5000001],n,k;
int qsort(int L,int R,int k)
{
    if(L==R) 
    {
        return a[L];    
    }
    int num=a[rand()%(R-L+1)+L];
    int i=L,j=R;
    while(i<=j)
    {
        while(a[i]<num)i++;
        while(a[j]>num)j--;
        if(i<=j) 
        {
            swap(a[i],a[j]);
            i++;
            j--;

        }
    }
    if(j-L+1>=k)
        return qsort(L,j,k);
    else if(k<=i-1) return num;
    else return qsort(i,R,k-(i-L));
} 
int main()
{
    scanf("%d%d",&n,&k);
    k++;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    cout<<qsort(1,n,k);
}

by 逸之为一 @ 2021-09-03 17:02:22

你K<=i-1不能直接return num啊! 还要继续递归!


|