60分求助

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

liaodong0812 @ 2022-01-01 23:04:54

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define NN 20000005
int a[NN];
int n;
void qsort(int left,int right) {
    int i=left,j=right;
    int mid=a[(i+j)/2];
    while(i<=j){
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;j--;
        }
    }
    if(i<right)qsort(i,right);
    if(j>left)qsort(left,j);
}
int main()
{
    int k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    qsort(1,n);
    cout<<a[k+1];
    return 0;
}

by shiroko2008 @ 2022-01-02 09:20:36

@liaodong0812 O(nlogn)会TLE,请用O(n)


by liaodong0812 @ 2022-01-02 22:39:47

@bugwriter 我就是想问怎么优化【捂脸】


by shiroko2008 @ 2022-01-03 10:52:06

1.找到一个基准点T 
2.使T左边的元素小于等于T,右边大于T 
3.根据T的下标与k-1的大小关系,选择在左边或右边递归 
4.若T的下标=k-1,输出T,递归中止

|