一、题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你
可以按 任意顺序 返回答案。

二、示例

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

输入: nums = [1], k = 1
输出: [1]

三、思路
本题采用的算法思路是最小堆。
四、代码展示

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
class MinHeap {
    constructor() {
        this.heap = []
    }
    addOne(value) {
        this.heap.push(value)
        this.shiftUp(this.heap.length - 1)
    }
    shiftUp(index) {
        if (index === 0) return
        let parentIndex = this.getParentIndex(index)
        if (this.heap[parentIndex] && this.heap[index] && this.heap[parentIndex].value > this.heap[index].value) {
            this.swap(index, parentIndex)
            this.shiftUp(parentIndex)
        }
    }
    getParentIndex(index) {
        return Math.floor((index - 1) / 2)
    }
    swap(index1, index2) {
        let temp = this.heap[index1]
        this.heap[index1] = this.heap[index2]
        this.heap[index2] = temp
    }
    pop() {
        if (this.heap.length <= 1) {
            this.heap.shift()
            return
        }
        this.heap[0] = this.heap.pop()
        this.shiftDown(0)
    }
    shiftDown(index) {
        let leftChildIndex = this.getLeftChildIndex(index)
        let rightChildIndex = this.getRightChildIndex(index)
        if (this.heap[leftChildIndex] && this.heap[index] && this.heap[leftChildIndex].value < this.heap[index].value) {
            this.swap(index, leftChildIndex)
            this.shiftDown(leftChildIndex)
        }
        if (this.heap[rightChildIndex] && this.heap[index] && this.heap[rightChildIndex].value < this.heap[index].value) {
            this.swap(index, rightChildIndex)
            this.shiftDown(rightChildIndex)
        }
    }
    getLeftChildIndex(index) {
        return index * 2 + 1
    }
    getRightChildIndex(index) {
        return index * 2 + 2
    }
    size() {
        return this.heap.length
    }
}
var topKFrequent = function (nums, k) {
    let map = new Map()
    let newHeap = new MinHeap()
    for (let item of nums) {
        if (map.has(item)) {
            map.set(item, map.get(item) + 1)
        } else {
            map.set(item, 1)
        }
    }
    map.forEach((value, key) => {
        newHeap.addOne({ value, key })
        if (newHeap.size() > k) {
            newHeap.pop()
        }
    })
    return newHeap.heap.map((item) => item.key)
};

五、总结