题意
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入:[3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入:[3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
思路及解答
堆排序
这道题就是经典的 topK 问题， 实现一个小根堆，规定堆的元素大小是 k 个，将比堆顶大的元素进堆。最后遍历完数组之后，此时堆顶是 k 个元素中最小的，有就是所有元素中第 k 大的了。
可以用PriorityQueue的最小堆来实现：
升序排序后索引为 len - k 的元素
其实题目已经告诉我们了：
你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
因此，升序排序以后，返回索引为 len - k 这个元素即可。
代码如下：
时间复杂度：O(NlogN)。这里 N 是数组的长度，算法的性能消耗主要在排序，JDK 默认使用快速排序，因此时间复杂度为O(NlogN)。
空间复杂度：O(1)。这里是原地排序，没有借助额外的辅助空间。
但是，如果出了这道题，显然不是想让你调 API，而是看你对快排的理解
借助快排 partition 操作定位（推荐）
“快速排序” 中的 partition(切分)操作简单介绍如下：
对于某个索引i，nums[i] 已经排序完，即 nums[i] 经过 partition(切分)操作以后会放置在它 “最终应该放置的地方”；
nums[left] 到 nums[i - 1] 中的所有元素都不大于 nums[i]；
nums[i + 1] 到 nums[right] 中的所有元素都不小于 nums[i]。
很显然，nums[i] 最终所在的位置，也就是它排序后的具体位置。也就是说，如果实现的排序是降序排序，那么第k个位置的数据，也确定就是第k大的
而这样每经过一次 partition操作就能缩小搜索的范围，这样的思想叫做 “减而治之”(是 “分而治之” 思想的特例)。下面是参考代码：
时间复杂度：O(N)。这里 N 是数组的长度。
空间复杂度：O(1)。切分过程可以不借助额外的数组空间，仅通过交换数组元素实现，没有借助额外的辅助空间。