怎么缩短时间复杂度啊

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:08:42

@gavinliu266 为什么我记得基于比较的排序算法理论时间复杂度的下限就是 n \log n。

by xiao7_Mr_10_ @ 2024-07-16 10:08:48

@gavinliu266 是这样的

by gavinliu266 @ 2024-07-16 10:09:14

加上三分区中就是 O(n) 了。

by _Hzx_ @ 2024-07-16 10:09:18

@xiao7_Mr10 归并

by xiao7_Mr_10_ @ 2024-07-16 10:09:45

@Hzx 噗，不是的

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

问题在于那不是排序，只需要找出第 k 大就可以了。所以最终数列不一定是有序的。

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

@gavinliu266 是的

by _Hzx_ @ 2024-07-16 10:11:57

@gavinliu266 好吧，我刚想说我们一直讨论的是排序不是问题本质（）

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

这只是快排的思想，不是快速排序。

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

我并没有说这题正解是快速排序