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$。
第二行包含 $n$ 个整数,表示数组的元素,每个元素满足 $1 ≤ a_i < 10^9$。
输出格式
输出一个整数,表示数组中第 k 小的数。
输入输出样例
输入 #1
5 1 4 3 2 1 5
输出 #1
2