怎么缩短时间复杂度啊

KonjacTeng @ 2024-07-16 09:45:23

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,k,num[5000000];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&num[i]);
    sort(num,num+n);
    printf("%d",&num[k]);
    return 0;
}

by gavinliu266 @ 2024-07-16 10:19:32

只不过是分成两部分，然后根据数的排名选择其中一部分，这并不是快速排序。

by gavinliu266 @ 2024-07-16 10:19:49

@Hzx

by gavinliu266 @ 2024-07-16 10:21:18

如果您认为我是直接快速排序后输出，那可能是您理解错了。

by _Hzx_ @ 2024-07-16 10:21:47

@gavinliu266 我懂，可能是因为讨论的问题不一样（）

就是分治，每次分成两半，然后就看第 k 小在哪部分进行排序对吧

by gavinliu266 @ 2024-07-16 10:28:56

嗯