LeetCode 692. 前K个高频单词

约 6 分钟
文章信息 14 个分类 10 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 字节跳动 微软 美团 阿里巴巴 腾讯 猿辅导 百度 京东 拼多多
标签
数组 字符串 哈希表 排序 堆（优先队列） 字典树 计数 Top N 问题 桶排序 小顶堆
目录

题目描述

✅ 692. 前 K 个高频单词

image-20250420085905359

题意分析

给定一个单词数组和整数 k，要求返回出现次数最多的 k 个单词，并且返回的这个列表本身也必须是有序的。

排序规则是两层的，这是整道题的核心信息：第一层按出现次数从多到少；第二层，当两个单词次数相同时，按字典序从小到大。两层的方向恰好相反——次数是降序，字典序是升序。绝大多数错误都出在没有把这个「方向相反」当回事。

从约束里能读出几个信号。答案是「前 k 个」而不是「全部」，说明存在只维护 k 个候选的优化空间；同时题目保证 k 不超过不同单词的数量，所以不需要处理「候选不够 k 个」的情况。单词是字符串而非整数，比较代价不再是常数，而是 $O(L)$（$L$ 为单词长度），复杂度分析时严格来说要带上这个因子。此外结果要求有序，这一点会直接影响堆解法——堆弹出的顺序和答案要求的顺序是反的。

边界情形包括：所有单词各不相同，此时次数全为 1，答案退化为「字典序最小的 k 个」；所有单词完全相同，此时不同单词只有一个，k 必然为 1；以及 k 恰好等于不同单词总数，此时相当于把所有单词排一遍序。

解法：哈希计数后排序

核心思路

问题关键：先消除重复单词，再按两级规则排序：频次降序；频次相同时字典序升序。两级方向相反，比较器是本题重点。

为什么选排序：哈希表一次统计频次，只对 u 个不同单词排序，代码短、顺序直接正确。若 k 远小于 u，容量为 k 的堆可降为 $O(u\log k)$，但比较器方向和最终输出顺序都更容易写错；本题约束下排序版更适合作为面试主解法。

比较规则与不变量：比较 a、b 时，先用 Integer.compare(freq[b], freq[a]) 让高频在前；相等时用 a.compareTo(b) 让字典序小的在前。排序后，列表任意前项都不劣于后项，因此前 k 项恰好是有序答案。使用 Integer.compare 而不是频次相减，可避免一般场景中的整数溢出并满足比较器契约。

正确性：哈希表给出每个不同单词的准确频次；比较器完整实现题目的唯一顺序。全量排序后，比第 k 项更优的单词不可能留在后缀，所以截取前缀不会遗漏或多取。

解题步骤

  1. 遍历 words，用哈希表统计每个单词的出现次数。
  2. 将哈希表的键放入列表，只排序不同单词。
  3. 比较两个单词时，先比较频次；仅在频次相等时比较字典序。
  4. 排序完成后返回左闭右开区间 [0, k)。

口述样例：["i","love","leetcode","i","love","coding"]、k=2 的频次为 i:2、love:2、leetcode:1、coding:1。排序时前两者按字典序得到 i、love，答案为 ["i","love"]。

边界检查：所有频次都是 1 时，答案应是字典序最小的 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 个引用；不重复拷贝输入字符串。排序实现所需栈或辅助空间不改变该上界。

关键点总结

  • 只排序哈希表中的不同单词，避免重复项占据多个名额。
  • 多级比较必须逐级判断：频次降序，字典序升序；不要让第二级跟着第一级一起反向。
  • Java 比较整数优先用 Integer.compare，避免用减法实现比较器。
  • 若追问堆解法：容量为 k 的堆顶要放“最差候选”——低频优先淘汰，同频时字典序较大的优先淘汰；最后弹出的顺序还需反转。

易错点总结

  • 频次写成升序：["i","i","love"]、k=1 会错误返回低频的 "love"。
  • 同频时写成字典序降序：i 与 love 都出现两次时会得到 ["love","i"]。
  • 直接排序原数组：重复单词会重复占据前 k 个位置，必须排序去重后的键集合。
  • 用 freq.get(b) - freq.get(a) 比较：在通用大数据场景可能整数溢出，应使用 Integer.compare。
  • 将切片上界写成 k-1：subList 和 Go 切片都是左闭右开，应取 [0,k)。

相似题目

题目 难度 考察点
347. 前 K 个高频元素 中等 本题去掉字典序这一层，只有单层规则，且答案顺序任意，可直接桶排序
451. 根据字符出现频率排序 中等 同样是计数后按频次排序，但要输出全部字符并按频次展开成字符串，没有 k 截断
215. 数组中的第K个最大元素 中等 不做频次统计，只求第 k 大的单个值，可用快速选择做到期望 $O(n)$
973. 最接近原点的 K 个点 中等 比较键需要现算距离平方而非查表，且方向是取最小的 k 个，堆的方向随之相反
LCR 060. 前 K 个高频元素 中等 347 的同题换皮，可用来检验计数加堆的模板是否已经写熟
LCR 076. 数组中的第 K 个最大元素 中等 215 的同题换皮，重点在快速选择的分区实现而非比较器设计
剑指 Offer 40. 最小的k个数 简单 求最小的 k 个，须改用容量 k 的最大堆淘汰，是堆方向取反的最简练习
面试题 17.14. 最小K个数 中等 与剑指 40 同题，数据规模更大，更适合对比堆与快速选择的实际耗时