LeetCode215. 数组中的第K个最大元素-一一网

题目描述

在未排序的数组中找到第 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 ≤ 数组的长度。
复制代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
 /**
    解题思路： 
        看到 第K个最大元素，考虑使用最小堆
    解题步骤：
        构建一个最小堆，并依次把数组的值插入到堆中
        当堆的容量超过K,就删除堆顶
        插入结束后，堆顶就是第k个最大元素
  */
class MinHeap {
  constructor() {
    this.heap = []
  }

  swap (i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  }
  getParentIndex (i) {
    return (i - 1) >> 1
  }
  getLeftIndex (i) {
    return i * 2 + 1
  }
  getRightIndex (i) {
    return i * 2 + 2
  }

  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)
    }
  }

  shiftDown (index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)

    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }

    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }

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

  pop () {
    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 h = new MinHeap()
    nums.forEach(i => {
        h.insert(i)
        if(h.size() > k) {
            h.pop()
        }
    })
    return h.peek()
};

// 题目转载自力扣官网：
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
复制代码