数组中的第K个最大元素
给定整数数组 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
思路
找到数组中第K大的元素，我们最直观的思路，肯定是把数组排个序，然后取第K大的元素就好了，但是题目中要求，必须使用O(n)的时间复杂度处理，而一般内置的排序算法，是无法满足O(n)的，因此我们需要想别的办法。
说到O(n)，说明题目是希望我们仅使用一次遍历就可以找到第N大的元素，一遍遍历就能找到第K大的元素，是不可能的事情，那么我们的思考方向，尽量往这个方向靠，尽可能少的遍历，找到第K大的元素。
我们可以借用二分的思想，只不过需要对二分做一些变种处理，在数组中随机选择一个数，我们就叫它中间数，然后进行分堆处理，比中间数大的，我们就将其放入大堆中，等于它的放入中间堆，小于它的放入小堆，然后判断第K大的数应该在哪一个堆中，在对其进行递归查找。
class Solution {private int findKthLargest(int[] nums, int k) {List<Integer> numList = new ArrayList<>();for (int num : nums) {numList.add(num);}return quickSelect(numList, k);}private int quickSelect(List<Integer> nums, int k) {// 随机选择基准数Random rand = new Random();int pivot = nums.get(rand.nextInt(nums.size()));// 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中List<Integer> big = new ArrayList<>();List<Integer> equal = new ArrayList<>();List<Integer> small = new ArrayList<>();for (int num : nums) {if (num > pivot)big.add(num);else if (num < pivot)small.add(num);elseequal.add(num);}// 第 k 大元素在 big 中，递归划分if (k <= big.size())return quickSelect(big, k);// 第 k 大元素在 small 中，递归划分if (big.size() + equal.size() < k)return quickSelect(small, k - (big.size() + equal.size()));// 第 k 大元素在 equal 中，直接返回 pivotreturn pivot;}
}