题目描述

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

注意：

• 你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
• 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

格式

输入

• 第一行输入一个n，表示要输入几个数。
• 第二行包含 n 个元素。
• 第三行一个整数 k。

输出

• 数组排序后的第 k 个最大的元素。

示例

输入：

6
3 2 1 5 6 4
2
5

输出：

5

输入：

9
3 2 3 1 2 4 5 5 6
4

输出：

4

提示

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4