题目描述

给定一个长度为 n 的整数数组 nums 和一个整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

也就是说，数组中的重复元素需要重复计算。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入描述

第一行输入两个整数 n 和 k，分别表示数组长度和需要寻找的第 k 大元素。

第二行输入 n 个整数，表示数组 nums。

输出描述

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

输入样例

6 2
3 2 1 5 6 4

输出样例

5

样例解释

将数组从大到小排序后为：

6 5 4 3 2 1

其中第 2 个最大的元素是 5，因此输出 5。

数据范围

$1 <= k <= n <= 100000$

$-1000000000 <= nums[i] <= 1000000000$