LeetCode 347. 前 K 个高频元素

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 347. 前 K 个高频元素

思路分析

这个解法的关键是使用最小堆来维护前 K 高频元素。首先，我们统计每个元素的频率，然后遍历频率统计字典。如果堆的大小小于 K，我们直接将元素加入堆。否则，如果当前元素的频率大于堆顶元素的频率，我们将堆顶元素弹出，再将当前元素加入堆。这样，堆中始终保持着前 K 高频元素。

参考代码

type Element struct {
	num       int
	frequency int
}

// 定义一个最小堆
type MinHeap []Element

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].frequency < h[j].frequency }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Element))
}

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

func topKFrequent(nums []int, k int) []int {
	// 使用哈希表统计每个元素的频率
	frequencyMap := make(map[int]int)
	for _, num := range nums {
		frequencyMap[num]++
	}

	// 使用最小堆来维护频率最高的前 k 个元素
	h := &MinHeap{}
	heap.Init(h)
	for num, frequency := range frequencyMap {
		heap.Push(h, Element{num, frequency})
		if h.Len() > k {
			heap.Pop(h)
		}
	}

	// 提取最小堆中的元素，即前 k 高频元素
	res := make([]int, k)
	for i := k - 1; i >= 0; i-- {
		res[i] = heap.Pop(h).(Element).num
	}

	return res
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/07679557