LeetCode 692. 前K个高频单词

Categories:

Tags:

题目描述
思路分析
1. 解法一：哈希表 + 排序（推荐）
2. 解法二：哈希表 + 最小堆
相似题目

题目描述

✅ 692. 前 K 个高频单词

思路分析

解法一：哈希表 + 排序（推荐）

核心思路：

用哈希表统计每个单词出现的频率。

将所有单词按自定义规则排序：频率高的排在前面，频率相同时按字典序升序排列。

取排序后的前 k 个单词即为结果。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示单词总数，排序的时间复杂度为 O(n log n)。

空间复杂度：O(n)，其中 n 表示单词总数，用于存储哈希表和排序数组。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 统计每个单词出现的频率
        Map<String, Integer> freqMap = new HashMap<>();
        for (String word : words) {
            freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
        }

        // 将所有单词放入列表，按频率降序、字典序升序排序
        List<String> candidates = new ArrayList<>(freqMap.keySet());
        candidates.sort((a, b) -> {
            int freqA = freqMap.get(a);
            int freqB = freqMap.get(b);
            // 频率不同时，频率高的排前面
            if (freqA != freqB) {
                return freqB - freqA;
            }
            // 频率相同时，字典序小的排前面
            return a.compareTo(b);
        });

        // 取前 k 个单词
        return candidates.subList(0, k);
    }
}

import "sort"

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

    // 将所有单词放入切片
    candidates := make([]string, 0, len(freqMap))
    for word := range freqMap {
        candidates = append(candidates, word)
    }

    // 按频率降序、字典序升序排序
    sort.Slice(candidates, func(i, j int) bool {
        freqI := freqMap[candidates[i]]
        freqJ := freqMap[candidates[j]]
        // 频率不同时，频率高的排前面
        if freqI != freqJ {
            return freqI > freqJ
        }
        // 频率相同时，字典序小的排前面
        return candidates[i] < candidates[j]
    })

    // 取前 k 个单词
    return candidates[:k]
}

解法二：哈希表 + 最小堆

核心思路：

用哈希表统计每个单词的频率。

维护一个大小为 k 的最小堆：堆顶是当前 k 个候选中”最不优先”的元素（频率最小，频率相同时字典序最大）。

遍历哈希表，当堆大小超过 k 时弹出堆顶，最终堆中保留最优的 k 个单词。

将堆中结果逆序输出，得到最终答案。

复杂度分析：

时间复杂度：O(n log k)，其中 n 表示单词总数，每次堆操作的时间复杂度为 O(log k)。

空间复杂度：O(n + k)，其中 n 表示哈希表大小，k 表示堆的大小。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 统计每个单词出现的频率
        Map<String, Integer> freqMap = new HashMap<>();
        for (String word : words) {
            freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
        }

        // 最小堆：堆顶为当前 k 个候选中最不优先的元素
        // 比较规则：频率小的在堆顶；频率相同时，字典序大的在堆顶
        PriorityQueue<String> minHeap = new PriorityQueue<>((a, b) -> {
            int freqA = freqMap.get(a);
            int freqB = freqMap.get(b);
            if (freqA != freqB) {
                return freqA - freqB;
            }
            // 字典序大的排在堆顶（更容易被淘汰）
            return b.compareTo(a);
        });

        // 遍历所有单词，维护大小为 k 的最小堆
        for (String word : freqMap.keySet()) {
            minHeap.offer(word);
            // 堆大小超过 k 时，弹出最不优先的元素
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // 从堆中取出结果并逆序
        List<String> result = new LinkedList<>();
        while (!minHeap.isEmpty()) {
            result.add(0, minHeap.poll());
        }
        return result;
    }
}

import (
    "container/heap"
)

// WordItem 表示单词和其出现频率
type WordItem struct {
    word string
    freq int
}

// MinHeap 实现最小堆接口
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].freq < h[j].freq
    }
    // 频率相同时，字典序大的在堆顶（更容易被淘汰）
    return h[i].word > h[j].word
}

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[:n-1]
    return x
}

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

    // 维护大小为 k 的最小堆
    h := &MinHeap{}
    heap.Init(h)

    for word, freq := range freqMap {
        heap.Push(h, WordItem{word, freq})
        // 堆大小超过 k 时，弹出最不优先的元素
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    // 从堆中取出结果并逆序
    result := make([]string, k)
    for i := k - 1; i >= 0; i-- {
        result[i] = heap.Pop(h).(WordItem).word
    }
    return result
}

相似题目

题目	难度	考察点
347. 前 K 个高频元素	中等	堆 / 桶排序 / 哈希表
215. 数组中的第K个最大元素	中等	堆 / 快速选择
451. 根据字符出现频率排序	中等	堆 / 桶排序
703. 数据流中的第 K 大元素	简单	小顶堆 / 数据流
373. 查找和最小的 K 对数字	中等	堆 / 多路归并
1636. 按照频率将数组升序排序	简单	哈希表 / 排序

本文作者: HGNULB

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