347. 前 K 个高频元素

[swiftwind0405]

方法一：最小堆

解题思想：

• 先把数组转换成频率的数组
• 遍历这个数组，将值插入堆中

代码：
最小堆的类：

class MinHeap {
    constructor() {
        this.heap = [];
    }

    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    
    getLeftIndex(i) {
        return 2 * i + 1;
    }

    getRightIndex(i) {
        return 2 * i + 2;
    }

    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = 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) {
        if (index > this.heap.length - 1) return;
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }

    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }

    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0)
    }

    peek() {
        return this.heap[0];
    }

    size() {
        return this.heap.length;
    }
}

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

    return h.heap.map(a => a.key);
};

复杂度分析：

• 时间复杂度：O(n*logK)
• 空间复杂度：O(n)，构建了一个最大长度为N长度的字典，以及一个长度为K的堆，因此空间复杂度是 K + n。