Skip to main content

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

题目描述​

给定整数数组 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

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

解题方法​

方法一：最小堆​

  • 思路

    • 求第k个最大元素，需要先对数组排序，再找出第K个最大元素，可以考虑使用最小堆

  • 步骤

    • 把数组的值插入最小堆中
    • 当堆容量超过K时,删除堆顶
    • 插入结束，堆顶就是第K个最大元素
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
class MinHeap {
  constructor() {
    this.heap = []
  }

  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }

  getParentIndex (index) {
    return (index - 1) >> 1
  }

  shiftUp(index) {
    if (index === 0) {
      return
    }
    const parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }

  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }

  getLeftIndex(index) {
    return index * 2 + 1
  }

  getRightIndex(index) {
    return index * 2 + 2
  }

  shiftDown(index) {
    const getLeftIndex = this.getLeftIndex(index)
    const getRightIndex = this.getRightIndex(index)
    if (this.heap[getLeftIndex] < this.heap[index]) {
      this.swap(getLeftIndex, index)
      this.shiftDown(getLeftIndex)
    }
    if (this.heap[getRightIndex] < this.heap[index]) {
      this.swap(getRightIndex, index)
      this.shiftDown(getRightIndex)
    }
  }

  pop() {
    if (this.size() === 0) {
      return
    }
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
  }

  peek () {
    return this.heap[0]
  }

  size() {
    return this.heap.length
  }
}
var findKthLargest = function(nums, k) {
    const heap = new MinHeap()
    nums.forEach(x => {
        heap.insert(x)
        if (heap.size() > k) {
            heap.pop()
        }
    })
    return heap.peek()
};