题目内容

给定一个由整数构成的数组 nums 和一个正整数 k，请返回该数组按数值从大到小排序后，位于第 k 位的元素。这里的位次从 1 开始计数。

需要注意，题目不要求对元素去重：排序后相同的数值会连续出现，并各自占据一个位置，因此重复值在计数时也需要被重复计算。

你需要实现时间复杂度为 $O(n)$ 的算法来解决此问题。

约束条件：

• 数组长度 $n$ 满足 $1 \le k \le n \le 10^5$。
• 数组中每个元素的绝对值不超过 $10^9$。

输入描述

输入包含两个参数：

• nums：一个整数数组，表示待查找的数组。
• k：一个整数，表示目标位置序号。

输出描述

返回一个整数，表示将 nums 按从大到小排序后第 k 位的元素。

样例1

输入

7 3
5 5 1 2 3 4 4

输出

4

说明

将数组按从大到小排序后为 5、5、4、4、3、2、1。其中前两个 5 分别占据第 1 位和第 2 位，因此第 3 位是 4。重复元素各自占据位置，需要重复计数。

样例2

输入

1 1
-42

输出

-42

说明

数组只有一个元素 -42，排序后仍然是 -42。由于 $k=1$，第 1 大的元素就是 -42。

样例3

输入

5 5
-1 -2 -3 -4 -5

输出

-5

说明

数组按从大到小排序后为 -1、-2、-3、-4、-5。第 5 位是 -5。

当 $k=n$ 时，需要返回排序后的最后一个元素，也就是数组中的最小值。