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

题目

LeetCode 中等

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

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

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

题解

方法：快排的优化版

时间复杂度：O(n)
空间复杂度：O(logn)

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,
      'startIndex',
      start,
      'midIndex',
      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 = [3,2,1,5,6,4],
  k = 4
console.log('🌰', findKthLargest(nums, k))

执行结果

♻️  [3,2,1,5,6,4]
targetIndex 2 startIndex 0 midIndex 3 midNum 5
leftArr [3,2,1,4] rightArr [6]
♻️  [3,2,1,4]
targetIndex 2 startIndex 0 midIndex 2 midNum 1
leftArr [] rightArr [3,2,4]
♻️  [3,2,4]
targetIndex 2 startIndex 1 midIndex 1 midNum 2
leftArr [] rightArr [3,4]
♻️  [3,4]
targetIndex 2 startIndex 2 midIndex 1 midNum 4
leftArr [3] rightArr []
♻️  [3]
🌰 3

方法：堆排序

时间复杂度：O(nlogn)
空间复杂度：O(logn)

function findKthLargestHeap(nums, k) {
  console.log([...nums])

  let heapSize = nums.length
  buildMaxHeap(nums, heapSize)

  console.log('📌', [...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) {
    console.log('交换', arr[i], arr[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))

执行结果

[3,2,3,1,2,4,5,5,6]
交换 1 6
交换 3 5
交换 2 6
交换 2 5
交换 3 6
交换 3 5
📌 [6,5,5,3,2,4,3,2,1]
交换 6 1
交换 1 5
交换 1 3
交换 1 2
📌 8 [5,3,5,2,2,4,3,1,6]
交换 5 1
交换 1 5
交换 1 4
📌 7 [5,3,4,2,2,1,3,5,6]
交换 5 3
交换 3 4
📌 6 [4,3,3,2,2,1,5,5,6]
🌰 4

本页目录