怎么缩短时间复杂度啊

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 _Hzx_ @ 2024-07-16 09:58:58

打->大

by xinxin2022 @ 2024-07-16 09:59:08

@Hzx 如果是lxl造的数据就更完了

by xiao7_Mr_10_ @ 2024-07-16 09:59:13

@Hzx .....

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

@Hzx 笑死我了，自己看代码,等会发

by _Hzx_ @ 2024-07-16 10:01:00

@xiao7_Mr10 所以你写一下你的神奇快排代码吧，如果真是接近 O(n)，当我傻逼就好了。不过我始终不相信快排能不被卡到 O(n)。

by WydnksqhbD @ 2024-07-16 10:01:04

@Hzx 大佬呀，拉链法怎么可能被卡成 O(n)？可以证明概率笑道可以忽略不计。而且 sort 超越 O(n\log n) 的概率比你的电脑被雷劈中的概率要小得多。

by WydnksqhbD @ 2024-07-16 10:01:52

@Hzx 散列表怎么你了？

by WydnksqhbD @ 2024-07-16 10:02:30

反正空间够，你用拉链 + 红黑树不行吗？

by _Hzx_ @ 2024-07-16 10:02:30

@WydnksqhbD 你是不是没听懂我的话，我说了会被卡成 O(n) 吗，我好像只说过会被卡成 O(n \log n) 吧。

by WydnksqhbD @ 2024-07-16 10:03:07

@Hzx 不好意思看错了。那么我认为用堆排序最好。