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

链接：215.数组中的第K个最大元素
难度：Medium
标签：数组、分治、快速选择、排序、堆（优先队列）
简介：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

题解 1 - typescript

• 编辑时间：2020-06-29
• 执行用时：88ms
• 内存消耗：35.9MB
• 编程语言：typescript
• 解法介绍：构建大顶堆即可。

class Heap {
  get size(): number {
    return this._elemenets.length;
  }
  constructor(private _elemenets: number[]) {
    this.heapify();
  }
  heapify(): void {
    for (let i = (this.size >> 1) - 1; i >= 0; i--) {
      this.siftDown(i);
    }
  }
  remove(): number {
    const root = this._elemenets[0];
    this._elemenets[0] = this._elemenets.pop() as number;
    this.siftDown(0);
    return root;
  }
  siftDown(index: number) {
    const element = this._elemenets[index];
    const half = this.size >> 1;
    while (index < half) {
      let childIndex = (index << 1) + 1;
      let child = this._elemenets[childIndex];
      const rightIndex = childIndex + 1;
      if (rightIndex < this.size && this._elemenets[rightIndex] > child) {
        child = this._elemenets[(childIndex = rightIndex)];
      }
      if (element >= child) break;
      this._elemenets[index] = child;
      index = childIndex;
    }
    this._elemenets[index] = element;
  }
}
function findKthLargest(nums: number[], k: number): number {
  const heap = new Heap(nums);
  for (let i = 1; i < k; i++) {
    heap.remove();
  }
  return heap.remove();
}