top-k-frequent-elements

https://leetcode.cn/problems/top-k-frequent-elements/description/

使用排序的方法

function topKFrequentSort(nums: number[], k: number): number[] {
  const frequencyMap = new Map<number, number>();

  // 统计每个数字的频率
  for (const num of nums) {
    frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
  }

  // 将频率映射转换为数组并按频率降序排序
  const sortedFrequencies = Array.from(frequencyMap.entries()).sort(
    (a, b) => b[1] - a[1],
  );

  // 返回前k个高频元素
  return sortedFrequencies.slice(0, k).map((entry) => entry[0]);
}
console.log(topKFrequentSort([1, 1, 1, 2, 2, 3], 2)); // 输出: [1,2]
console.log(topKFrequentSort([1], 1)); // 输出: [1]

使用最小堆的方法（更优化, 该阶段可以不用看）

• Prerequisite: You should have a basic understanding of heap data structures and their implementation in JavaScript.
  • Tree data structure
  • Heap data structure

class MinHeap {
  private heap: [number, number][] = [];

  push(val: [number, number]): void {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop(): [number, number] {
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  private bubbleUp(index: number): void {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex][1] > this.heap[index][1]) {
        [this.heap[parentIndex], this.heap[index]] = [
          this.heap[index],
          this.heap[parentIndex],
        ];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  private bubbleDown(index: number): void {
    while (true) {
      let smallestIndex = index;
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;

      if (
        leftChild < this.heap.length &&
        this.heap[leftChild][1] < this.heap[smallestIndex][1]
      ) {
        smallestIndex = leftChild;
      }
      if (
        rightChild < this.heap.length &&
        this.heap[rightChild][1] < this.heap[smallestIndex][1]
      ) {
        smallestIndex = rightChild;
      }

      if (smallestIndex !== index) {
        [this.heap[index], this.heap[smallestIndex]] = [
          this.heap[smallestIndex],
          this.heap[index],
        ];
        index = smallestIndex;
      } else {
        break;
      }
    }
  }

  get size(): number {
    return this.heap.length;
  }
}

function topKFrequentHeap(nums: number[], k: number): number[] {
  const frequencyMap = new Map<number, number>();

  // 统计每个数字的频率
  for (const num of nums) {
    frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
  }

  const minHeap = new MinHeap();

  // 维护一个大小为k的最小堆
  for (const [num, freq] of frequencyMap.entries()) {
    if (minHeap.size < k) {
      minHeap.push([num, freq]);
    } else if (freq > minHeap.heap[0][1]) {
      minHeap.pop();
      minHeap.push([num, freq]);
    }
  }

  // 返回堆中的元素（即为前k个高频元素）
  return minHeap.heap.map((entry) => entry[0]);
}

// 测试
console.log(topKFrequentHeap([1, 1, 1, 2, 2, 3], 2)); // 输出: [1,2]
console.log(topKFrequentHeap([1], 1)); // 输出: [1]