题解 | #47.寻找第K大#

借助快排，最开始我直接选取第一个元素为划分基准，但是超时，

function findKth(a, n, K) {
  function swap(i, j) {
    let tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }
  function find(left, right) {
    if(right-left<=0)  return a[left];
    
    let base = a[left];
    
    let i = left,j = right;

    while (i < j) {
      while (a[++i] < base);
      while (a[--j] >= base);
      if (i < j) swap(i, j);
      else break;
    }

    
    let trueIndex = i-1;
    swap(trueIndex,left);

    if (trueIndex == K) 
      return a[i];
    else if (trueIndex < K)//小于k在右边继续查找
      return find(trueIndex + 1, right);
    else  //大于k在左边继续查找
      return find(left, trueIndex - 1);
  }
  K = n - K;
  return find(0, n - 1);
}
module.exports = {
  findKth: findKth,
};

然后更改取基准的方法，选取left、center、right三个元素中大小排在中间的元素作为划分基准

function findKth(a, n, K) {
  function swap(i, j) {
    let tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }
  function median3(left, right) {
    let center = Math.floor((left + right) / 2);
    if (a[left]   > a[center] )  swap(left, center);
    if (a[left]   > a[right]  )  swap(left, right);
    if (a[center] > a[right]  )  swap(center, right);
    //此时 array[left] < array[center] < array[right]

    swap(center, right - 1); //将基准Pivot藏到右边，藏到right-1这个位置

    return a[right - 1];
  }
  function find(left, right) {
    if(right-left<=0)  return a[left];
    
    let base = median3(left,right);
    
    let i = left,j = right - 1;//left一定比基准小，right-1=基准

    while (i < j) {
      while (a[++i] < base);
      while (a[--j] >= base);
      if (i < j) swap(i, j);
      else break;
    }

    
    swap(i, right-1);

    if (i == K) 
      return a[i];
    else if (i < K)//小于k在右边继续查找
      return find(i + 1, right);
    else//大于k在左边继续查找 
      return find(left, i - 1);
  }
  K = n - K;
  return find(0, n - 1);
}

最简单的做法直接调库

findKth(a, n, K){
	a = a.sort((item1,item2)=>item1-item2);
	return a[n-K];
}

注意：right-left<=0的时候注意不要直接return，快排return的意思是不在排序，而这里需要返回array[left]