描述

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

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

要求：时间复杂度 O(nlogn)，空间复杂度 O(1)

示例

输入：[1,3,5,2,2], 5, 3
返回值：2

输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3
返回值：9
说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9  

思路

这道题目已经给了非常明显的提示，使用快速排序的算法去解决。 题目要求是寻找第K大, 我们以 [10,10,9,9,8,7,5,6,4,3,4,2] 这个数组为测试用例，排序后 [2,3,4,4,5,6,7,8,9,9,10,10] 总共12个数字。

从小到大排序后，很容易想到的是第1大的数,其实就是倒数第一个数，第2大的数，其实就是倒数第二个数。依此类推，数组中第3大的数。其实就是数组中的倒数第3个值。

在数组中如何取出倒数第k个元素

这里还是使用归纳的方法来求：

倒数第一个数，对应的索引是 数组的 length - 1 假设数组的长度是5，k = 1 对应的索引的其实是4，也就是 5-1 倒数第一个数，对应的索引是 数组的 length - 1 假设数组的长度是5，k = 2 对应的索引的其实是3，也就是 5-2 倒数第一个数，对应的索引是 数组的 length - 1 假设数组的长度是5，k = 3 对应的索引的其实是2，也就是 5-3

归纳法 yyds

/**
 * 
 * @param a int整型一维数组 
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
function findKth( a, n, K ) {
  let sortarr = quicksort(a)
  return sortarr[n-K]
}
// 快速排序
function quicksort(arr) {
  // 采用递归的形式，那这里的边界条件需要写好
  if(arr.length <= 1) {
    return arr
  }
  
  let left= [];
  let right = [];
  let index = Math.floor(arr.length / 2)
  let privot = arr.splice(index,1)[0]
  
  for(let i = 0; i < arr.length; i++ ){
    if(arr[i] < privot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quicksort(left).concat([privot],quicksort(right))
}
module.exports = {
  findKth : findKth
};