zhangdizhangdi

215.数组中的第K个最大元素

题目

LeetCode 中等

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：
输入: [3,2,1,5,6,4], k = 2
输出: 5

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

题解

方法：快排的优化版

O(n) O(logn)

js
function findKthLargest(nums, k) {
  const quickSelect = (arr, targetIndex, start) => {
    console.log(arr)

    if (arr.length <= 1) return arr[0] //直接返回

    let leftArr = []
    let rightArr = []
    const mid = Math.floor(arr.length / 2)
    const midNum = arr[mid]

    for (let i = 0; i < arr.length; i++) {
      if (i === mid) continue
      if (arr[i] > midNum) {
        rightArr.push(arr[i])
      } else {
        leftArr.push(arr[i])
      }
    }

    console.log(
      'targetIndex',
      targetIndex,
      'start',
      start,
      'mid',
      mid,
      'midNum',
      midNum,
    )
    console.log('leftArr', leftArr, 'rightArr', rightArr)

    if (leftArr.length + start === targetIndex) {
      return midNum
    } else if (leftArr.length + start > targetIndex) {
      //继续在“小”组里找
      return quickSelect(leftArr, targetIndex, start)
    } else {
      //继续在“大”组里找
      return quickSelect(rightArr, targetIndex, leftArr.length + start + 1)
    }
  }

  return quickSelect(nums, nums.length - k, 0)
}

const nums = [10, 46, 1, 6, 5],
  k = 4
console.log('🌰', findKthLargest(nums, k))
执行结果
[ 10, 46, 1, 6, 5 ]
targetIndex 1 start 0 mid 2 midNum 1
leftArr [] rightArr [ 10, 46, 6, 5 ]
[ 10, 46, 6, 5 ]
targetIndex 1 start 1 mid 2 midNum 6
leftArr [ 5 ] rightArr [ 10, 46 ]
[ 5 ]
🌰 5

方法：堆排序

O(nlogn) O(logn)

js
function findKthLargestHeap(nums, k) {
  let heapSize = nums.length
  buildMaxHeap(nums, heapSize)

  console.log('init maxHeap', [...nums])

  for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
    swap(nums, 0, i)
    --heapSize
    maxHeapify(nums, 0, heapSize)
    console.log('', i, [...nums])
  }
  return nums[0]

  // 自下而上构建一颗大顶堆
  function buildMaxHeap(nums, heapSize) {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(nums, i, heapSize)
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(nums, i, heapSize) {
    let l = i * 2 + 1
    let r = i * 2 + 2
    let largest = i
    if (l < heapSize && nums[l] > nums[largest]) {
      largest = l
    }
    if (r < heapSize && nums[r] > nums[largest]) {
      largest = r
    }
    if (largest !== i) {
      swap(nums, i, largest)
      maxHeapify(nums, largest, heapSize)
    }
  }
  //交换
  function swap(arr, i, j) {
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
}

const nums = [3, 2, 3, 1, 2, 4, 5, 5, 6],
  k = 4
console.log('🌰', findKthLargestHeap(nums, k))
执行结果
init maxHeap [
  6, 5, 5, 3, 2,
  4, 3, 2, 1
]
 8 [
  5, 3, 5, 2, 2,
  4, 3, 1, 6
]
 7 [
  5, 3, 4, 2, 2,
  1, 3, 5, 6
]
 6 [
  4, 3, 3, 2, 2,
  1, 5, 5, 6
]
🌰 4