怎么缩短时间复杂度啊

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 xinxin2022 @ 2024-07-16 10:03:23

知粥所重这题应当使用线段树，稳定的 n log n。

by _Hzx_ @ 2024-07-16 10:03:45

@WydnksqhbD 而且我也没说过 sort 复杂度超过 O(n \log n) 啊，请您擦亮您的眼睛再来回答，不带着脑子和眼睛和容易误会他人的。

by _Hzx_ @ 2024-07-16 10:05:10

@WydnksqhbD 堆也带 \log。

by xiao7_Mr_10_ @ 2024-07-16 10:05:25

@Hzx zz

by gavinliu266 @ 2024-07-16 10:06:36

@xiao7_Mr10 的类似快排确实是 O(n) 的 @Hzx

by _Hzx_ @ 2024-07-16 10:06:43

@WydnksqhbD 红黑树固然好，不过写的很难受，感觉 set 更方便，毕竟 set 内部实现就是红黑树。（况且我说过用set吧）

by xiao7_Mr_10_ @ 2024-07-16 10:06:51

@Hzx 等等，你说的分治法好像就是快排求 k-th

by xiao7_Mr_10_ @ 2024-07-16 10:07:26

@Hzx 利用快排思想选取基准数，然后看位置然后递归处理

by _Hzx_ @ 2024-07-16 10:07:50

@gavinliu266 准确来说 O(n) or O(n \log n)，可能会卡。

by gavinliu266 @ 2024-07-16 10:08:16