LeetCode 192. 统计词频

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

题目描述

✅ 192. 统计词频

image-20260928233516637

题意分析

从 words.txt 读取由小写字母组成的单词，单词之间有一个或多个空白分隔。要求统计每个单词的总出现次数，并按照词频降序输出 单词 次数。题目保证各词频率不同，因此不需要额外规定并列顺序。

输入按行组织，但统计对象是单词；相同单词还可能散落在不同位置。需要先拆成一词一行，再让相同词相邻，才能交给只统计连续重复行的 uniq -c。最后按计数重新排序，而不是保留字典序。

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

核心思路

[!blue]

整条管道依次改变记录的含义，每一级的输出正好符合下一级的输入要求：

  1. tr -s '[:space:]' '\n' 将空白转换成换行，并压缩连续换行，得到一词一行。文件开头若有空白，仍可能形成空行，所以接上 awk 'NF'，只保留字段数非零的记录。
  2. 第一次 sort 按单词排序，使同一个词的所有出现位置连续。uniq -c 才能一次数完整组，输出 次数 单词。
  3. sort -k1,1nr 以第一列为唯一排序键，n 表示按数值比较，r 表示逆序，也就是按频次从大到小。
  4. 最后的 awk '{print $2, $1}' 调换两列，使用默认空格分隔，输出题目要求的格式。

两次排序不可混为一次：前一次是在计数前聚集相同单词，后一次是在计数后决定输出顺序。计数尚未产生时，没有可供按频次排序的列。

解题步骤

  1. 通过 < words.txt 将文件送给 tr，把空白分隔的文本拆成单词记录。
  2. 过滤空记录，避免把空白当作一个单词。
  3. 按词排序并用 uniq -c 计数，此时每个不同单词恰好对应一行。
  4. 按计数列做数值降序排序，再交换计数与单词两列。

样例计数后为 day 1、is 3、sunny 2、the 4 这四组词频，最终按照 4、3、2、1 的顺序输出。文件没有有效单词时，空记录被过滤，后续管道自然没有输出。

代码实现

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

复杂度分析

设总字符数为 $N$，单词总数为 $W$，不同单词数为 $U$。拆词、计数和格式化需要线性扫描，主要开销来自两次排序。

  • 时间复杂度：若一次排序比较按常数成本计，整体为 $O(N + W\log(W+1) + U\log(U+1))$。若单词很长，还需要计入字典序比较实际读取的字符数。
  • 空间复杂度：中间记录与排序数据的总规模为 $O(N)$；sort 可以采用外部排序，将部分中间数据放在临时磁盘上，因此不能把所有排序存储都简单视为常驻内存。

关键点总结

[!green]

  • uniq 的“重复”指相邻行重复，先排序才能得到整个文件的总词频。
  • uniq -c 将计数放在第一列，最终必须交换成单词在前。
  • 最终排序必须是数值降序，字符串字典序无法正确处理两位数及更大的计数。
  • 代码中的反斜杠只用于跨行展示，整个过程仍是一条 Unix 管道。

易错点总结

[!yellow]

  • 不拆词就直接排序：排序与计数的对象会变成整行文本，而不是单词。
  • 不排序就执行 uniq -c：同一个词若被别的词隔开，会分成多个计数组，无法得到总频次。
  • 不排除空记录：输入开头或连续空白可能让空行参与计数，产生并不存在的单词。
  • 第二次排序不加 n：词频会按字符顺序比较，可能把 10 排在 2 后面。
  • 交换列后仍按第一列做数值排序：第一列已经是单词，应先按计数排序，再格式化输出。

相似题目

题目 难度 关联与区别
692. 前K个高频单词 中等 同样统计词频并按频次排序，原题只返回前K项，本题输出全部不同词及次数。
451. 根据字符出现频率排序 中等 同样先聚合频次再排序，本题对象是单词，原题对象是字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/30895416
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！