LeetCode 692. 前K个高频单词

Categories:

Tags:

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

题目描述

✅ 692. 前 K 个高频单词

思路分析

小顶堆

参考代码

type WordItem struct {
	word string
	freq int
}

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

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
	if h[i].freq == h[j].freq {
		return h[i].word > h[j].word // 字典序较大的排在后面
	}
	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.(WordItem))
}

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

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

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

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

	res := make([]string, 0, k)
	for h.Len() > 0 {
		res = append(res, heap.Pop(h).(WordItem).word)
	}

	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
	return res
}

时间复杂度：O (n log k)，其中 n 是单词的数量。

我们需要遍历单词并将每个单词插入堆中，堆的操作时间复杂度为 O (log k)。

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

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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