怎么缩短时间复杂度啊

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 xiao7_Mr_10_ @ 2024-07-16 09:46:36

我有一法！快速排序!

by xiao7_Mr_10_ @ 2024-07-16 09:46:49

@xiao7_Mr10 复杂度近似O(n)

by _Hzx_ @ 2024-07-16 09:47:42

@xiao7_Mr10 实际上快排是带 \log 的，很容易被卡成 \log。

by _determination_ @ 2024-07-16 09:47:58

@xiao7_Mr10 ？？？

by xinxin2022 @ 2024-07-16 09:48:22

@xiao7_Mr10 有没有一种可能他用的就是快速排序

by xiao7_Mr_10_ @ 2024-07-16 09:48:51

@Hzx 哥们，我说的是类似快排的方法，你们没学过???

by xinxin2022 @ 2024-07-16 09:49:21

@tengzichen 这题是练分治的

快排也能卡过

by xiao7_Mr_10_ @ 2024-07-16 09:49:23

@xiao7_Mr10 基准数归位后判断其位置，然后只递归一边，近似O(n)啊老底

by ouxiyao @ 2024-07-16 09:50:09

printf("%d",&num[k]); 不用&吧？

by _Hzx_ @ 2024-07-16 09:50:46

@xiao7_Mr10 哥，快排不具有稳定性，会被卡的，出题人没你想的那么傻。另外 sort 不就是快排吗？