LeetCode 192. 统计词频

约 3 分钟
文章信息 2 个分类 1 个标签
分类
LeetCode 中等
标签
Shell
目录

题目描述

✅ 192. 统计词频

题意分析

文件 words.txt 只包含小写字母和空格，每个单词由一个或多个空格分隔。要求统计每个单词出现的次数，并按词频从高到低输出 单词 次数。题目保证不同单词的词频互不相同，因此不必定义并列时的次级排序规则。

输入是“多行、每行多个词”，而 uniq -c 只能统计连续相同的行。所以管道需要完成三次语义转换：先把所有单词拆成“一词一行”，再排序让相同词相邻并计数，最后按计数重新降序排列。

官方样例中 the、is、sunny、day 分别出现 4、3、2、1 次，最终输出顺序正好是 the 4、is 3、sunny 2、day 1。

解法：拆词、聚合、按频次排序

核心思路

tr -s '[:space:]' '\n' 把空格和原换行统一转换成换行，并压缩连续分隔符，从而得到一词一行的数据流。awk 'NF' 再过滤可能出现的空记录，使开头、结尾或连续空白不会被当成单词。

第一次 sort 按单词字典序排列，目的不是最终展示，而是让所有相同词相邻；只有这样 uniq -c 才能得到全局词频。uniq -c 输出格式是 次数 单词。

第二次 sort -k1,1nr 只按第一列计数做数值降序排列。最后一个 awk 交换两列，恢复题目要求的 单词 次数。

管道不变量是：每通过一级命令，记录仍然完整，只改变一种维度——分词、按词归并、计数、按次数排序、格式化。调换任意两步都可能改变含义。

解题步骤

  • 将所有空白分隔符转换成换行，得到一词一行。
  • 过滤空行，避免空字符串参与统计。
  • 按单词排序，让相同单词相邻。
  • 用 uniq -c 对每组连续相同单词计数。
  • 按计数列数值降序排序。
  • 交换“次数”和“单词”两列后输出。

代码实现

tr -s '[:space:]' '\n' < words.txt \
    | awk 'NF' \
    | sort \
    | uniq -c \
    | sort -k1,1nr \
    | awk '{print $2, $1}'

复杂度分析

设文件总字符数为 $N$、单词数为 $W$、不同单词数为 $U$。

  • 时间复杂度：分词和计数管道为 $O(N+W)$；第一次排序为 $O(W \log W)$，第二次排序为 $O(U \log U)$，总计 $O(N + W \log W + U \log U)$，通常由第一次排序主导。
  • 空间复杂度：从算法视角为 $O(W)$，排序需要保存或外排中间记录；实际 sort 会按内存限制使用临时磁盘，因此大文件下应同时关注临时磁盘空间。

关键点总结

  • uniq 只合并相邻重复行，所以它前面的按词排序是正确性的必要条件。
  • 两次 sort 目的不同：第一次按词聚类，第二次按次数输出，不能合并。
  • -n 表示数值排序，缺少它会按字符串比较计数，例如 10 可能排在 2 后面。
  • 重定向 < words.txt 比 cat words.txt | ... 少启动一个无必要进程，也更直接表达输入来源。
  • 若面试官取消“词频互不相同”的保证，可把第二次排序改成 sort -k1,1nr -k2,2，在频次相同时按单词升序，得到确定性输出。

易错点总结

  • 直接执行 uniq -c 而不先排序：输入 the day the 会得到两个独立的 the 1，而不是 the 2。
  • 只把普通空格替换成换行却忽略原换行：跨行数据可能保留在同一处理分支里；使用 [:space:] 可统一空格与换行。
  • 不压缩或过滤空白记录：连续空格、文件首尾空白可能产生空行，进而统计出一个不存在的“空单词”。
  • 先格式化成 单词 次数 再执行 sort -nr：数值排序默认从行首读取，此时行首是单词，所有数值键都近似为 0，无法按词频排列。
  • 最终排序缺少 -n：词频 10 和 2 会按字符而非数值比较，顺序错误。
  • 把 sort | uniq -c 两步反过来：先计数只能得到局部连续频次，之后排序无法修复已经拆开的计数。

相似题目

题目 难度 考察点
193. 有效电话号码 简单 用正则从逐行文本中筛选合法记录
194. 转置文件 中等 用 awk 按字段重组二维文本
195. 第十行 简单 按行号选择记录，并处理文件行数不足