LeetCode 692. 前K个高频单词

2026-07-23 HGNULB 约 8 分钟

文章信息 18 个分类 8 个标签

分类

LeetCode CodeTop 中等未解决 20-50 腾讯字节阿里华为微软美团拼多多京东百度快手深信服 TP-LINK 猿辅导

题目描述

✅ 692. 前 K 个高频单词

题意分析

统计每个不同单词的出现次数，返回排名最高的 k 个不同单词。排名先按频次从高到低，再在频次相同的单词之间按字典序从小到大排列；这套规则既决定谁能入选，也决定输出顺序。

相同单词只占一个名额，k 不超过不同单词的数量。单词仅由小写英文字母组成，可以直接使用字符串的字典序比较；题目还要求考虑用堆把选择成本降到与 log k 相关。

解法一：哈希计数后排序

核心思路

[!blue]

先把重复出现的单词合并到频次表 freq。输入数组中的每次出现都会让计数加一，而进入排序列表的每个单词只保留一份，这样前 k 项才代表 k 个不同单词。

排序比较器直接表达答案顺序：频次不同，让较高频次排在前面；只有频次相同时，才让字典序较小者排在前面。第二级规则不能推翻第一级结果，因此比较完频次只要不相等就立即返回。

完整排序后，任意排在前面的单词都不劣于后面的单词，前 k 项自然就是所需答案，并且已经按要求排列。该方法同时完成选出候选和整理顺序，适合先把题目的排名规则实现清楚。

解题步骤

遍历 words，用哈希表统计每个单词的出现次数。

将频次表中的键放入列表，每个不同单词只出现一次。

按频次降序排序；频次相同时，按字典序升序排序。

返回排序列表的左闭右开区间 [0, k)。当 k 等于不同单词数时，返回整个有序列表。

代码实现

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freq = new HashMap<>();

        for (String word : words) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }

        List<String> unique = new ArrayList<>(freq.keySet());

        unique.sort(
                (first, second) -> {
                    int countCompare = Integer.compare(freq.get(second), freq.get(first));

                    if (countCompare != 0) {
                        return countCompare;
                    }

                    // 频次相同按字典序升序，两个排序条件都必须满足。
                    return first.compareTo(second);
                });

        return unique.subList(0, k);
    }
}

import "sort"

func topKFrequent(words []string, k int) []string {
    freq := make(map[string]int)
    for _, word := range words {
        freq[word]++
    }

    unique := make([]string, 0, len(freq))
    for word := range freq {
        unique = append(unique, word)
    }
    sort.Slice(unique, func(i, j int) bool {
        if freq[unique[i]] != freq[unique[j]] {
            return freq[unique[i]] > freq[unique[j]]
        }
        // 频次相同按字典序升序，两个排序条件都必须满足。
        return unique[i] < unique[j]
    })

    return unique[:k]
}

复杂度分析

设 n 为单词总数，u 为不同单词数，L 为单词最大长度。

时间复杂度：期望 $O(nL + uL\log u)$。统计需要计算字符串哈希，排序有 $O(u\log u)$ 次比较，最坏每次字典序比较扫描 $O(L)$ 个字符。通常将字符串操作视为常数时，写作 $O(n+u\log u)$。

空间复杂度：$O(u)$，哈希表和键列表各保存 u 个引用；不重复拷贝输入字符串。排序实现所需栈或辅助空间不改变该上界。

关键点总结

[!green]

只排序哈希表中的不同单词，避免重复项占据多个名额。

多级比较必须逐级判断：频次降序，字典序升序；不要让第二级跟着第一级一起反向。

Java 比较整数优先用 Integer.compare，避免用减法实现比较器。

解法二：大小为 k 的堆

核心思路

[!blue]

完整排序还会排列用不到的其余单词。若只保留最好的 k 个，可以让堆顶代表当前候选中最差的一项，便于新单词加入后立即淘汰它。

这里的“最差”要同时考虑两条规则：频次更小者更差；频次相同时，字典序更大者更差。因此堆的比较器采用频次升序、同频字典序降序，与最终答案的排序方向恰好相反。

每处理一个不同单词，先将它加入堆。若堆大小超过 k，删除堆顶。这时被删除的是此前候选与新单词中最差的一项，剩余仍是所有已处理单词中最好的 k 个；原先已经淘汰的单词也不可能因为加入新词重新进入前 k，所以不必保存。

扫描完后堆中就是答案集合，但堆内部并非有序列表。连续弹出堆顶得到的是从差到好的顺序，因此将弹出的单词从结果下标 k - 1 向零填写，才能同时满足频次降序与同频字典序升序。

解题步骤

用哈希表统计每个不同单词的频次。

建立频次升序、同频字典序降序的淘汰比较器。

遍历不同单词，入堆后若大小超过 k，弹出最差候选。

从结果下标 k - 1 到零依次填写弹出的单词，恢复所需顺序。

代码实现

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freq = new HashMap<>();

        for (String word : words) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<String> heap =
                new PriorityQueue<>(
                        (a, b) -> {
                            int byCount = Integer.compare(freq.get(a), freq.get(b));

                            // 堆顶放最差候选，同频时字典序更大的先淘汰。
                            return byCount != 0 ? byCount : b.compareTo(a);
                        });

        for (String word : freq.keySet()) {
            heap.offer(word);

            if (heap.size() > k) {
                heap.poll();
            }
        }

        String[] answer = new String[k];

        // 弹出顺序从差到好，倒着写入结果才能得到题目排序。
        for (int i = k - 1; i >= 0; i--) {
            answer[i] = heap.poll();
        }

        return Arrays.asList(answer);
    }
}

import "container/heap"

type wordCount struct {
    word  string
    count int
}

type wordHeap []wordCount

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

func (h wordHeap) Less(i, j int) bool {
    if h[i].count != h[j].count {
        return h[i].count < h[j].count
    }
    // 堆顶放最差候选，同频时字典序更大的先淘汰。
    return h[i].word > h[j].word
}

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

func (h *wordHeap) Push(x any) { *h = append(*h, x.(wordCount)) }

func (h *wordHeap) Pop() any {
    old := *h
    last := old[len(old)-1]
    *h = old[:len(old)-1]
    return last
}

func topKFrequent(words []string, k int) []string {
    freq := make(map[string]int)
    for _, word := range words {
        freq[word]++
    }

    h := &wordHeap{}
    for word, count := range freq {
        heap.Push(h, wordCount{word, count})
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    answer := make([]string, k)
    // 弹出顺序从差到好，倒着写入结果才能得到题目排序。
    for i := k - 1; i >= 0; i-- {
        answer[i] = heap.Pop(h).(wordCount).word
    }
    return answer
}

复杂度分析

时间复杂度：期望 $O(nL + uL \log(k + 1))$，n 为总单词数、u 为不同单词数、L 为最长单词长度，包含计数和比较字符串的成本。

空间复杂度：$O(u + k)$，保存计数表、候选堆和结果引用，不复制单词文本。

关键点总结

[!green]

比较方向按淘汰规则定义：堆顶应是最低频、同频中字典序最大的候选。

只让不同单词入堆：先完成计数，再遍历计数表，不能让同一单词占多个位置。

反向填写结果：淘汰顺序与最终输出顺序相反，不能直接按出堆顺序追加。

易错点总结

[!yellow]

最终排序的频次要降序，同频字典序要升序，不能把两级比较一起反向。

应遍历频次表中的不同单词来排序或入堆，不能让重复出现的同一个词占据多个名额。

堆顶是待淘汰的最差候选，同频时应优先弹出字典序更大的词，不能照搬答案比较器。

不能直接遍历堆或按出堆顺序追加答案；连续出堆是从差到好，应倒着填写。

subList 和 Go 切片的上界不包含在结果中，取前 k 项应写 [0, k)。

相似题目

题目	难度	关联与区别
347. 前 K 个高频元素	中等	同样频次统计后选TopK，本题同频时还要按单词字典序排序。
451. 根据字符出现频率排序	中等	原题按频次输出所有字符，本题只返回前k个不同单词并明确并列规则。
补充题 199. 前 K 个高频单词及词频	中等	都先统计词频并按频次与字典序排序；补充题还在结果中返回词频。
215. 数组中的第K个最大元素	中等	用大小受限的堆保留排名靠前的候选；本题以单词频次和字典序联合排序，该题以数值为排序依据选择第 k 大。
703. 数据流中的第 K 大元素	简单	用大小受限的堆保留排名靠前的候选；本题以单词频次和字典序联合排序，该题支持持续插入时维护第 k 大。
973. 最接近原点的 K 个点	中等	用大小受限的堆保留排名靠前的候选；本题以单词频次和字典序联合排序，该题以到原点的平方距离为排序依据。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

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

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！