0192. Word Frequency

题目信息

题号:
  1. 统计词频

难度:

Medium

主题:

Shell、文本流、分组计数、数值排序

原题:

LeetCode 0192

重点:

先把任意空白分隔文本规范为每词一行,再排序聚组、计数并调整输出字段

题目重述

编写 Bash 脚本读取当前目录中的 words.txt。文件包含若干单词,单词之间由一个或多个 空白字符分隔。

统计每个不同单词在整个文件中的出现次数,每行输出 word count,并按次数从高到低 排列。相同次数之间没有指定顺序。

自建示例

words.txt:
red   blue red
green blue red
blue

一种合法输出:
blue 3
red 3
green 1

连续空格和换行都只是分隔符,计数范围跨越全部行。

Bash 实现

#!/usr/bin/env bash

export LC_ALL=C

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

题解

原始输入的记录粒度不对

Shell 工具通常按行处理,但题目的逻辑记录是“一个单词”。如果直接对文件行排序或去重, "red blue" 会被当成一个整体,既不能跨行统计,也不能区分同一行中的多个词。

可以先收集所有不同单词,再为每个单词重新扫描文件计数;这样同一文本会被读取多次,工作 量随不同单词数增长。主脚本改为一次管道:每一阶段只解决一种数据形态转换,并把结果流给 下一阶段。

第一阶段:每个单词变成一行

tr -s '[:space:]' '\n' 把空格、制表符、换行等空白统一映射为换行,-s 再把连续 换行压成一个。于是无论原文件如何换行或使用多个空格,输出都变成:

red
blue
red
green
blue
red
blue

输入重定向 < words.txt 只把文件内容送入标准输入,不把文件名本身当作普通参数或 输出。空文件及只有空白的文件不会产生单词记录。

题目按空白定义单词,所以标点和大小写不会被额外规范化:Word 与 word 是两个 不同词,word, 中的逗号也属于词本身。脚本不擅自加入题目之外的清洗规则。

第二阶段:让相同记录相邻

uniq -c 只能合并 相邻 的相同行,不能在整条流中寻找分散重复项。若直接对上一步 结果执行 uniq,三个 blue 被其他词隔开,无法合并。

第一个 sort 按单词排列,使相同词形成连续组;uniq -c 随后把每组压缩成一行, 并把计数放在前面:

3 blue
1 green
3 red

这两个命令共同完成“按单词分组并统计”,不能删除或交换顺序。

第三阶段:按数字而不是文本排序

uniq -c 的当前字段顺序是 count word。sort -k1,1nr 只使用第一字段,n 表示 数值比较,r 表示降序。若遗漏 n,文本排序会把 10 当作排在 2 前后的字典文本, 无法保证频次顺序。

-k2,2 只作为次数相同时的单词升序次关键字,使输出稳定;题目不要求该顺序,但它不 违反主排序条件。LC_ALL=C 让字符排序规则不随运行环境区域设置变化,也不会改变计数。

最后,awk '{print $2, $1}' 把字段从 count word 调整成题目要求的 word count。 awk 的默认输出字段分隔符是一个空格,正好符合格式。

完整状态走读

示例经过各阶段的核心状态为:

空白规范化:red, blue, red, green, blue, red, blue(每项独占一行)
单词排序:  blue, blue, blue, green, red, red, red
聚组计数:  3 blue;1 green;3 red
数值降序:  3 blue;3 red;1 green
字段交换:  blue 3;red 3;green 1

每个阶段的输入不变量正是上一阶段的输出保证,因此无需在 awk 中再次解析原始文本或 维护复杂状态。

复杂度与方案选择

设共有 W 个单词。空白规范化和计数扫描为线性工作;主成本是单词排序,通常为 O(W log W),外部 sort 可使用临时文件处理超过内存的数据。也可用单个 awk 关联数组在线计数,再只排序 U 个不同单词;那会把全部频次状态放入内存。主脚本采用 标准 sort + uniq 流水线,阶段语义清楚,并利用 Shell 工具的外部排序能力。