使用快速排序 或者 大根堆两种方法(不考虑调用库)
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位置上就完成了一个维护过程。
