P1923 【深基9.例4】求第 k 小的数

XMDxmd0525 @ 2022-03-20 06:49:58

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int a[5000001], n, i, k;
int main(){
    cin>>n>>k;
    for(int j=0;j<n;j++) cin>>a[j];
    sort(a, a+n);
    cout<<a[k];
}

by hayzxjr @ 2022-03-20 06:54:25

改成scanf

by XiaoQuQu @ 2022-03-20 06:54:42

@XMDxmd0525 请不要因为低质量问题发布讨论 此题目由于 n\le 5\times 10^6 无法使用 sort 通过

by hayzxjr @ 2022-03-20 06:55:32

用nth_element

by inc1ude_c @ 2022-03-20 06:56:29

@XMDxmd0525 请先学习如何计算程序时间复杂度。

by huangzitai @ 2022-03-20 07:00:21

@XMDxmd0525 手写快排求第 k 小是 \displaystyle \mathcal O(n) 的

by XMDxmd0525 @ 2022-03-20 07:01:49

@XiaoQuQu 我没有你们厉害，行吧，我才刚刚接触编程半年，没学过sort, 用sort是做题经验，不过谢谢你提醒

by XMDxmd0525 @ 2022-03-20 07:02:19

@int524288 谢谢

by XMDxmd0525 @ 2022-03-20 07:02:39

@As_Water 谢谢，欧克

by XMDxmd0525 @ 2022-03-20 07:02:57

@incldue ok

by XiaoQuQu @ 2022-03-20 07:03:57

@XMDxmd0525 其实这种问题可以看题解，题解第一篇就指出了这个问题