LeetCode题练习与总结：统计词频--192

一、题目描述

写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。

为了简单起见，你可以假设：

• words.txt只包括小写字母和 ' ' 。
• 每个单词只由小写字母组成。
• 单词间由一个或多个空格字符分隔。

示例:

假设 words.txt 内容如下：

the day is sunny the the
the sunny is is

你的脚本应当输出（以词频降序排列）：

the 4
is 3
sunny 2
day 1

说明:

• 不要担心词频相同的单词的排序问题，每个单词出现的频率都是唯一的。
• 你可以使用一行 Unix pipes 实现吗？

二、解题思路

1. 读取文件 words.txt 的内容。
2. 使用 tr 命令将所有连续的空格替换为一个空格。
3. 再次使用 tr 命令将所有空格替换为换行符，这样每个单词就会单独一行。
4. 使用 sort 命令对单词进行排序，这样相同的单词会排列在一起。
5. 使用 uniq -c 命令统计每个单词出现的次数。
6. 使用 sort 命令按照次数降序排列。
7. 格式化输出，确保每个单词和其频率之间有一个空格，并且按照要求的格式输出。

三、具体代码

#!/bin/bash
 
# 读取文件内容，将连续空格替换为一个空格，将空格替换为换行，排序，统计频率，再排序，最后输出
cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -nr | awk '{print $2,$1}'

四、时间复杂度和空间复杂度

1. 时间复杂度

• cat words.txt: 这个命令的时间复杂度是 O(n)，其中 n 是文件 words.txt 的总字节数，因为它需要读取整个文件。

• tr -s ' ' '\n': 这个命令的时间复杂度是 O(n)，因为它需要遍历整个输入流来压缩连续的空格。

• sort: 排序的时间复杂度通常是 O(n log n)，其中 n 是输入行数。在最好的情况下（如果输入已经排序），它可以是 O(n)，但通常我们考虑最坏情况。

• uniq -c: 这个命令的时间复杂度是 O(n)，因为它需要遍历排序后的列表来计算每个单词的出现次数。

• sort -nr: 再次排序，时间复杂度同样是 O(n log n)。

• awk '{print $2,$1}': 这个命令的时间复杂度是 O(n)，因为它需要遍历所有输入行并打印它们。

总的时间复杂度是 O(n log n)，因为排序步骤是整个脚本中最耗时的部分。

2. 空间复杂度

• cat words.txt: 空间复杂度是 O(n)，因为它需要将整个文件内容存储在内存中。

• tr -s ' ' '\n': 空间复杂度是 O(n)，因为它需要存储处理后的结果。

• sort: 空间复杂度通常是 O(n)，因为排序算法需要额外的空间来存储数据。

• uniq -c: 空间复杂度是 O(n)，因为它需要存储每个单词及其计数。

• sort -nr: 再次排序，空间复杂度是 O(n)。

• awk '{print $2,$1}': 空间复杂度是 O(1)，因为它不需要额外的空间，只是重新格式化输入。

总的空间复杂度是 O(n)，因为脚本在任意时刻都需要存储文件的内容或其处理结果。

综上所述，该脚本的时间复杂度是 O(n log n)，空间复杂度是 O(n)。

五、总结知识点

• Shell脚本基础:

  • #!/bin/bash: 脚本声明，指定脚本应该使用Bash解释器来执行。

• 管道（Pipes）:

  • 使用管道（|）将一个命令的输出作为另一个命令的输入，实现命令的串联。

• 文件读取:

  • cat words.txt: 读取文件内容并输出到标准输出。

• 文本处理:

  • tr -s ' ' '\n': 使用 tr 命令替换（压缩）连续的空格为一个空格，并将所有空格替换为换行符。
  • -s 选项用于压缩连续的字符。

• 排序:

  • sort: 对输入进行排序，用于后续的 uniq 命令。
  • sort -nr: 对数字进行降序排序，-n 选项表示按照数值排序，-r 选项表示反向排序。

• 去重和计数:

  • uniq -c: 去除连续的重复行，并输出每个唯一行的出现次数。

• 文本格式化:

  • awk '{print $2,$1}': 使用 awk 命令来格式化输出，$2 和 $1 分别代表输入行的第二列和第一列。

• 正则表达式:

  • 虽然在这个脚本中没有直接使用正则表达式，但 tr 和 awk 命令支持正则表达式，这在更复杂的文本处理任务中很有用。

• 标准输入/输出:

  • 脚本中的命令默认从标准输入读取数据，并将结果输出到标准输出。

• 命令行选项:

  • 了解并使用命令行工具的各种选项，如 tr 的 -s 选项和 sort 的 -n 和 -r 选项。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。