347.前K个高频元素

链接：347.前K个高频元素
难度：Medium
标签：数组、哈希表、分治、桶排序、计数、快速选择、排序、堆（优先队列）
简介：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

题解 1 - typescript

• 编辑时间：2020-09-07
• 执行用时：108ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：构造堆进行遍历。

class Frequent {
  count = 1;
  constructor(public num: number) {}
}
class Heap<T> {
  get size(): number {
    return this._elemenets.length;
  }
  constructor(private _elemenets: T[], private compare: (e1: T, e2: T) => number) {
    this.heapify();
  }
  heapify(): void {
    for (let i = (this.size >> 1) - 1; i >= 0; i--) {
      this.siftDown(i);
    }
  }
  remove(): T {
    const root = this._elemenets[0];
    this._elemenets[0] = this._elemenets.pop() as T;
    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.compare(this._elemenets[rightIndex], child) > 0) {
        child = this._elemenets[(childIndex = rightIndex)];
      }
      if (this.compare(element, child) >= 0) break;
      this._elemenets[index] = child;
      index = childIndex;
    }
    this._elemenets[index] = element;
  }
}
function topKFrequent(nums: number[], k: number): number[] {
  const frequents: Record<number, Frequent> = {};
  for (const num of nums) {
    if (frequents[num]) frequents[num].count++;
    else frequents[num] = new Frequent(num);
  }
  const heap = new Heap(Object.values(frequents), (e1, e2) => e1.count - e2.count);
  const ans: number[] = [];
  while (k-- !== 0) {
    ans.push(heap.remove().num);
  }
  return ans;
}