692.前K个高频单词

链接：692.前K个高频单词
难度：Medium
标签：字典树、哈希表、字符串、桶排序、计数、排序、堆（优先队列）
简介：给一非空的单词列表，返回前 k 个出现次数最多的单词。

题解 1 - typescript

• 编辑时间：2021-04-09
• 执行用时：144ms
• 内存消耗：44.6MB
• 编程语言：typescript
• 解法介绍：构建堆。

class Heap<T> {
  private arr: T[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  get top() {
    return this.arr[0];
  }
  constructor(private compare: (num1: T, num2: T) => number) {}
  add(num: T): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): T {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  private shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  private shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 <= this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
}
function topKFrequent(words: string[], k: number): string[] {
  const map: Record<string, number> = {};
  for (const word of words) map[word] = (map[word] ?? 0) + 1;
  const strCheck = (str1: string, str2: string) => {
    let i = 0;
    while (str1[i] && str1[i] === str2[i]) i++;
    if (str1[i] && !str2[i]) return -1;
    else if (!str1[i] && str2[i]) return 1;
    else return str2.codePointAt(i)! - str1.codePointAt(i)!;
  };
  const heap = new Heap<[string, number]>(([str1, v1], [str2, v2]) =>
    v1 === v2 ? strCheck(str1, str2) : v1 - v2
  );
  Object.entries(map).forEach(v => heap.add(v));
  const ans: string[] = [];
  while (heap.size && k--) {
    ans.push(heap.remove()[0]);
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-05-20
• 执行用时：132ms
• 内存消耗：44.3MB
• 编程语言：typescript
• 解法介绍：利用堆去获取。

class Heap<T = number> {
  private arr: T[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  get top() {
    return this.arr[0];
  }
  constructor(private compare: (t1: T, t2: T) => number) {}
  add(num: T): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): T {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  private shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  private shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 <= this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
  *[Symbol.iterator](): IterableIterator<T> {
    for (const t of this.arr) {
      yield t;
    }
  }
}
function topKFrequent(words: string[], k: number): string[] {
  const map: Record<string, number> = {};
  for (const word of words) map[word] = (map[word] ?? 0) + 1;
  const chartToNumber = (char: string) => char.codePointAt(0)! - 'a'.codePointAt(0)!;
  const heap = new Heap<[string, number]>(([k1, v1], [k2, v2]) => {
    if (v1 !== v2) return v1 - v2;
    let i1 = 0;
    const end1 = k1.length;
    let i2 = 0;
    const end2 = k2.length;
    for (; i1 < end1 && i2 < end2; i1++, i2++)
      if (k1[i1] !== k2[i2]) return chartToNumber(k2[i2]) - chartToNumber(k1[i1]);
    if (i1 === end1) return 1;
    else if (i2 === end2) return -1;
    else return 0;
  });
  for (const data of Object.entries(map)) heap.add(data);
  const ans: string[] = [];
  while (heap.size !== 0 && k--) ans.push(heap.remove()[0]);
  return ans;
}