Skip to content

14372: 【原4372】Quick Select

题目

题目描述

author: sakiko 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4372

Description

对于给定的n个数$a_1, a_2,..., a_n$,输出这些数字中的第k小的数。(请不要使用STL)

Input Format

第一行是两个整数$n, k$,$n$表示数组的长度;
第二行是$n$个整数,表示数组$a_1,a_2,...,a_n$。

Output Format

输出$a_1,a_2,...,a_n$中第k小的数。

Sample Input 1

5 2
4 3 2 1 4

Sample Output 1

2

Sample Input 2

5 3
1 1 2 2 3

Sample Output 2

2

Data Range

对于$30\%$的数据,$n \le 100000$。
对于$100\%$的数据,$a_i \le 10^9$,$1 \le k \le n \le 5000000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!