剑指 Offer II 060. 出现频率最高的 k 个数字

力扣

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

示例 1:

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

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

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 

进阶：所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

维护一个大小为k的小顶堆，其中存储[出现次数，数字]的数组，先对数组进行遍历形成哈希表，然后再对哈希表的元素进行插入小顶堆的操作

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        numFreq = collections.Counter(nums)
        minHeap = []
        for x, freq in numFreq.items():
            heapq.heappush(minHeap, (freq, x))
            while len(minHeap) > k:
                heapq.heappop(minHeap)
        ans = []
        while minHeap:
            ans.append(heapq.heappop(minHeap)[1])
        return ans

type IHeap [][2]int

func (h IHeap) Len() int {
	return len(h)
}

func (h IHeap) Less(i, j int) bool {
	return h[i][1] < h[j][1]
}

func (h IHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func (h *IHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func topKFrequent(nums []int, k int) []int {
	mp := make(map[int]int)
	for _, v := range nums {
		mp[v]++
	}
	hp := &IHeap{}
	heap.Init(hp)
	for key, value := range mp {
		heap.Push(hp, [2]int{key, value})
		if hp.Len() > k {
			heap.Pop(hp)
		}
	}
	ret := make([]int, k)
	for i := k - 1; i > -1; i-- {
		ret[i] = heap.Pop(hp).([2]int)[0]
	}
	return ret
}