测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A1916. 求第 k 小的数

编程题 普及/提高-
知识点

题目描述

输入 $n$($1 \le n < 5000000$ 且 $n$ 为奇数)个数字 $a_i$($1 \le a_i < {10}^9$),输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。

输入格式

输入的第一行包含两个整数 n 和 k,其中 n 是数组的长度($1 ≤ n < 5,000,000 且 n 为奇数$),$k$ 是要找的第 $k$ 小的数的位置(最小的数是第 0 小)。
第二行包含 $n$ 个整数,表示数组的元素,每个元素满足 $1 ≤ a_i < 10^9$。

输出格式

输出一个整数,表示数组中第 k 小的数。

输入输出样例

输入 #1
5 1
4 3 2 1 5
输出 #1
2
上一题 去做题 下一题