TLE——我一生的痛

圣啦啦 @ 2020-11-29 22:36:42

by 圣啦啦 @ 2020-11-29 22:37:33

为各位大佬献上代码

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
int a[5000001];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int tot=0;
    if(k==0){
        cout<<a[0];
        return 0;
    }
    for(int i=1;i<n;i++){
        if(a[i]!=a[i-1]){
            tot++;
        }
        if(tot==k){
            cout<<a[i];
            break;
        }
    }
    return 0;
}

by Remake_ @ 2020-11-29 22:39:32

sort的时间复杂度是n\log n ，无法通过此题，需要写鸡排（（（

by hanzhongtlx @ 2020-11-29 22:50:45

cin,cout 有点虚啊....

by macrocosmos @ 2020-11-30 01:22:57

试试 std::ios::sync_with_stdio(false);。

如果还是不行的话建议手写快排，分治加快寻找第 k 小的数。

by fanypcd @ 2020-11-30 07:15:31

其实就是在快排的最后分治位置选一半，这样时间复杂度就是O(n/2+n/4....) = O(N)

参考CSP-J2020初赛阅读程序T2

效果和题目中所说的nth_element一样（时间复杂度也一样）

by dinglinxi0409 @ 2021-01-09 15:25:04

sort是可以的