描述

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

示例

输入：

[1,3,5,2,2],5,3

返回值：

2

输入：

[10,10,9,9,8,7,5,6,4,3,4,2],12,3

返回值：

9

思路

用快排+减枝

因为找第K个最大就是n个最小其中n=a.length-K

当mid<n，只需要对【mid+1----right】快排

当mid>n，只需要对【left----mid-1】进行快排

代码

/**
 * 
 * @param a int整型一维数组 
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
function findKth( a ,  n ,  K ) {
    // write code here
    quick(a,0,a.length-1,a.length-K);
    console.log(a);
    return a[a.length-K];
}
function quick(a,left,right,k)
{
    let mid=quicksort(a,left,right);
    if(k<mid&&mid>left){
        quick(a,left,mid-1,k);
    }
    if(k>mid&&mid<right){
        quick(a,mid+1,right,k);
    }
    if(k===mid){
        return 
    }
}
function quicksort(a,left,right)
{
    let item=a[left];
    while(left<right){
        while(left<right&&a[right]>=item) right--;
        a[left]=a[right];
        while(left<right&&a[left]<=item) left++;
        a[right]=a[left];
    }
    a[left]=item;
    return left;
}
module.exports = {
    findKth : findKth
};

 运行环境：Javascript Node

运行时间：56ms

占用内存：8248KB