LeetCode 347. 前 K 个高频元素

Categories:

Tags:

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

题目描述

✅ 347. 前 K 个高频元素

思路分析

小顶堆

参考代码

type Item struct {
	num  int
	freq int
}

type MinHeap []Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].freq < h[j].freq }
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.(Item))
}

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

func topKFrequent(nums []int, k int) []int {
	// 统计频率
	freqMap := make(map[int]int)
	for _, num := range nums {
		freqMap[num]++
	}

	// 使用最小堆
	h := &MinHeap{}
	heap.Init(h)

	for num, freq := range freqMap {
		heap.Push(h, Item{num, freq})
		if h.Len() > k {
			heap.Pop(h)
		}
	}

	res := make([]int, 0, k)
	for h.Len() > 0 {
		res = append(res, heap.Pop(h).(Item).num)
	}
	return res
}

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
}

时间复杂度：O (n log k)，其中 n 是数组的长度。

空间复杂度：O (n)，用于存储频率哈希表和堆。

func topKFrequent(nums []int, k int) []int {
	if len(nums) <= 0 {
		return nil
	}

	// 统计频率
	freqMap := make(map[int]int)
	for _, num := range nums {
		freqMap[num]++
	}

	// 小顶堆
	type pair struct {
		num  int
		freq int
	}

	// 手动实现一个小顶堆，使用 sort.Slice 维护堆结构
	heap := []pair{}
	for num, freq := range freqMap {
		heap = append(heap, pair{num, freq})
		// 排序使堆顶最小
		sort.Slice(heap, func(i, j int) bool {
			return heap[i].freq < heap[j].freq
		})
		// 超出 k 就弹出最小的
		if len(heap) > k {
			heap = heap[1:]
		}
	}

	var res []int
	for _, p := range heap {
		res = append(res, p.num)
	}
	return res
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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