题目内容

给定一个包含 $n$ 个整数的数组 $nums$ 和一个整数 $k$，请返回数组中第 $k$ 大的元素。

需要注意的是，第 $k$ 大表示将数组中的所有元素按照从大到小排序后位于第 $k$ 个位置的元素，而不是第 $k$ 个不同的元素。

数组中可能存在重复元素，重复元素需要分别参与排名。

要求设计并实现时间复杂度为 $O(n)$ 的算法解决该问题。

输入描述

第一行输入两个整数 $n$ 和 $k$，分别表示数组 $nums$ 的长度以及需要查找的排名。

第二行输入 $n$ 个整数 $nums_i$，表示数组中的各个元素，相邻整数之间用空格分隔。

约束

$1 \le k \le n \le 10^5$

$-10^4 \le nums_i \le 10^4$

输出描述

输出一个整数，表示数组 $nums$ 中第 $k$ 大的元素。

样例1

输入

6 2
3 2 1 5 6 4

输出

5

说明

将数组按照从大到小的顺序排列后为 $6,5,4,3,2,1$。

其中第 $2$ 大的元素为 $5$，因此输出 $5$。

样例2

输入

9 4
3 2 3 1 2 4 5 5 6

输出

4

说明

将数组按照从大到小的顺序排列后为 $6,5,5,4,3,3,2,2,1$。

重复元素需要分别参与排名，因此第 $4$ 大的元素为 $4$。