原文：215. 数组中的第K个最大元素(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0215/

题目：

难度：Middle

相关话题：堆、分治算法

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路：

  • sort排序。
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  // O(nlgn)
  nums.sort((a,b)=>b-a)
  return nums[k-1]
};
  • 二分法筛选。

每次选一个数，查看这个数能排第几位，如果更大则减小，更小则增大。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  // O(nlgn)
  k=nums.length-k+1
  let lo=Infinity,hi=-Infinity
  for(let i=0;i<nums.length;i++){
    if(nums[i]<lo)lo=nums[i]
    if(nums[i]>hi)hi=nums[i]
  }
  while(lo<hi){
    let mid=Math.floor((lo+hi)/2)
    let count=0
    for(let i=0;i<nums.length;i++){
      if(nums[i]<=mid)count++
    }
    if(count>=k)hi=mid
    else lo=mid+1
    }
  return lo
};
  • 使用快速选择。
  1. 快速排序我们都很清楚，每一次选中一个pivot，将小于它的放左边，大于它的放右边，执行lgN次。
  2. 快速选择同理，唯一的区别是当每次左右排序后，检查我们要找的值是在左边还是在右边，然后继续执行左或者右，另一边丢弃。
/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  return _qs(nums,0,nums.length-1,k)

  function _qs(arr,lo,hi,target){
    let i=lo,j=hi,pivot=arr[hi]
    while(i<j){
      if(arr[i]<pivot)i++
      else swap(arr,i,--j)
    }
    swap(arr,i,hi)
    // 数一下当前比 i 位置大的数量
    let curCount=hi-i+1
    // 当前数量和目标一致，返回
    if(curCount===target)return pivot
    // 当前数量更多，说明这个值偏小，需要在右边找
    else if(curCount>target)return _qs(arr,i+1,hi,target)
    // 当前数量更少，说明这个值偏大，需要在左边找，同时要减去已经找到的数量
    else return _qs(arr,lo,i-1,target-curCount)
  }
  function swap(arr,i,j){
    let t=arr[i]
    arr[i]=arr[j]
    arr[j]=t
  }
};

扩展阅读：