LeetCode 347（前 K 个高频元素）

通过堆的方式实现

• 时间复杂度：O (n * log k)

• 空间复杂度：O (n)

  function topKFrequent(nums, k) {
    const map = new Map();
    nums.forEach((n) => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1);
    });
    const h = new MinHeap();
    map.forEach((value, key) => {
        h.insert({ value, key });
        if (h.size() > k) {
            h.pop();
        }
    });
    return h.heap.map((x) => x.key);
  }

代码中有两个 forEach 循环，他们的时间复杂度分别是 O (n)，而我们知道堆的 insert 和 pop 的时间复杂度分别是 O (log k ) ，所以该函数的时间复杂度为 O (n * log k) k 代表数组中不相同元素的个数。空间复杂度是 O (n)，因为主要看 map 中存放不同元素的个数，最坏情况是 nums 数组的长度。

改造了一下堆构造函数

class MinHeap {
    constructor() {
        this.heap = [];
    }
    top() {
        return this.heap[0];
    }
    size() {
        return this.heap.length;
    }
    getChildLeftIndex(i) {
        return i * 2 + 1;
    }
    getChildRightIndex(i) {
        return i * 2 + 2;
    }
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    swap(index1, index2) {
        const temp = this.heap[index1];
        this.heap[index1] = this.heap[index2];
        this.heap[index2] = temp;
    }
    shiftUp(index) {
        if (index === 0) return;
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    shiftDown(index) {
        const leftChildIndex = this.getChildLeftIndex(index);
        const rightChildIndex = this.getChildRightIndex(index);
        if (this.heap[leftChildIndex] && this.heap[leftChildIndex].value < this.heap[index].value) {
            this.swap(leftChildIndex, index);
            this.shiftDown(leftChildIndex);
        }
        if (this.heap[rightChildIndex] && this.heap[rightChildIndex].value < this.heap[index].value) {
            this.swap(rightChildIndex, index);
            this.shiftDown(rightChildIndex);
        }
    }
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
}