使用快速排序 或者 大根堆两种方法(不考虑调用库)
1 快速排序
class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; int l = 0; int r = n - 1; while (true) { int idx = partition(nums, l, r); if (idx == k - 1) return nums[idx]; else if (idx < k - 1) l = idx + 1; else r = idx - 1; } } //----左右挖坑互填 public int partition(int [] nums, int l, int r) { int pivot = nums[l]; while (l < r) { while (l < r && nums[r] <= pivot) r --; nums[l] = nums[r]; while (l < r && nums[l] >= pivot) l ++; nums[r] = nums[l]; } nums[l] = pivot; return l; }}
快速排序每次选择下标为 l 的数为基准，将数组划分为大于l与小于l两部分，
在每次划分后l的位置就是从大到小排序的真实位置。
因此每完成一次快排的划分后，将最终的L返回，判断是否是k-1如果是k-1就证明当前L坐标的数时第K大的数
类似于二分，如果L小于K-1我们以INDEX+1，R为基准再快排一次，如果L大于K-1我们以L，INDEX-1再快排一次，这里的INDEX就是一次快排后L的最终值，但这是在函数里的，不影响全局变量L！！。
直到找到某次快排结束L = K-1 就返回答案。
2 大根堆
class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; build_maxHeap(nums); for (int i = 0; i < k - 1; i ++) { int tmp = nums[0]; nums[0] = nums[n-1-i]; nums[n-1-i] = tmp; adjust_down(nums, 0, n-1-i - 1); } return nums[0]; } public void build_maxHeap(int [] nums) { int n = nums.length; for (int root = n/2 - 1; root > -1; root --) { adjust_down(nums, root, n - 1); } } public void adjust_down(int [] nums, int root, int hi) { if (root > hi) return ; int t = nums[root]; int child = 2 * root + 1; while (child <= hi) { if (child + 1 <= hi && nums[child] < nums[child + 1]) child ++; if (t > nums[child]) break; nums[root] = nums[child]; root = child; child = 2 * root + 1; } nums[root] = t; }}
手动实现大根堆，之后将堆顶元素，也就是当前最大值，与尾部元素交换，然后我们只对除尾部外的部分，进行大根堆的维护，重复K-1次，再取出堆顶的元素也就是下表为0的值，他就是第K大值，要注意尾部是随着交换也在不断变大的，从长度为0增长到 k-1，在循环里用i来完成这个变化就行。
3 大根堆的介绍
大根堆本质还是数组，但是我们有一定的规则维护它，使得可以用数组 描绘出一个完全二叉树，在这个树内，父节点值大于其子节点值，而且我们按照层序遍历的顺序用数组下标与二叉树节点对应。
这样就可以得到大根堆的几个特性：
1 使用数组表示大根堆时，父节点i的左右子节点下标分别2i+1, 2i+2
2 下标最大的非叶子节点的下标为 数组长度n /2 - 1
因此 我们 使用两个方法，完成手动的大根堆(JAVA库里可以用优先队列完成)
1 生成大根堆
从 ROOT = N /2 -1 到 0 维护每一个非叶子节点，对每一个非叶子节点调用维护方法。
2 维护方法
需要当前节点下标 ，和 数组的结尾， 以及数组本身
2.1 然后先判断 当前节点是否超出想要的结尾，再记录当前节点值
2.2 判断左子树和右子树哪个值更大就向那个方向遍历
2.3 判断子树和本身值的大小，如果子树更大，就将子树的值覆盖到当前节点上，要注意当前节点的值是一直保存在单独的变量里
2.4 继续向下，遍历子树的子树，这个过程要将root 变为 child 然后 再更新 child = 2 *root +1
然后再回到2.1 开始下个循环。
在这个循环中，一旦子树比当前节点小，就停止循环跳出把之前一直保存的当前节点值，放到最新的ROOT位置上就完成了一个维护过程。