LeetCode 194. 转置文件
目录
题目描述
题意分析
给定一个按空格分隔的矩形文本表格，所有输入行的列数相同。要求把原来的每一列变成输出的一行，也就是执行矩阵转置。
输入
name age
alice 21
ryan 30有 3 行 2 列，转置后应有 2 行 3 列：
name alice ryan和age 21 30。
awk的NF表示当前行字段数，$i表示当前行第i个字段，天然适合按列收集。由于读取到一行时还不知道后续行同列的内容，单次扫描必须为每个输出列保存一个累积字符串，等文件读完后再输出。题目保证各行列数相同，因此在第一行保存
columns = NF，之后始终按这个列数处理。空文件会让columns保持 0，END中自然不输出任何内容。
解法：awk 按列累积
核心思路
用数组
transposed[i]保存原文件第i列到目前为止读到的所有字段。处理完前 $r$ 行后，不变量是：transposed[i]恰好由前 $r$ 行的第i个字段按顺序、以单个空格连接而成。第一行直接赋值
transposed[i] = $i，避免输出开头出现多余空格；从第二行开始用transposed[i] OFS $i追加，OFS默认就是空格。全部输入处理完成后，按列下标从 1 到
columns依次打印。输出顺序必须按列号，而不能遍历关联数组，因为关联数组遍历顺序没有保证。
解题步骤
- 在第一行记录总列数
columns = NF。- 对当前行的每个列下标
i，通过动态字段$i取得值。- 第一行初始化
transposed[i]，后续行在尾部追加空格和当前字段。END阶段按1..columns输出每个累积字符串。对样例，读完第一行后数组为
transposed[1] = "name"、transposed[2] = "age"；读完第二行变为"name alice"、"age 21"；读完第三行即得到最终两行。
代码实现
awk '
NR == 1 {
columns = NF
}
{
for (i = 1; i <= columns; i++) {
if (NR == 1) {
transposed[i] = $i
} else {
transposed[i] = transposed[i] OFS $i
}
}
}
END {
for (i = 1; i <= columns; i++) {
print transposed[i]
}
}
' file.txt
复杂度分析
设文件有 $R$ 行、$C$ 列，总文本长度为 $N$。
- 时间复杂度：按字段访问计为 $O(RC)$；若计入累积字符串在每次追加时的复制成本，最坏为 $O(RN)$。例如字段长度固定时 $N = \Theta(RC)$，该实现最坏为 $O(CR^2)$。
- 空间复杂度：$O(N)$，单次扫描需要保存全部转置结果后才能按列输出；按字段数记为 $O(RC)$。
关键点总结
$i是动态字段引用，表示当前记录的第i列；它不是数组下标语法。- 第一行应直接初始化，后续才追加
OFS，否则每个输出行会多一个前导空格。- 输出行数等于原列数，所以要保存第一行的
NF；NR是原行数，不能拿来控制输出列。- 必须按数值下标递增输出数组，不能依赖
for (i in transposed)的无序遍历。- 面试追问超大文件时可以说明：一遍扫描想立即输出转置结果就必须缓存；若内存不足，可以每次只输出一列并多次扫描文件，以更多 I/O 换更少内存。
易错点总结
- 首行误把数组名和字段引用拼成一个无效表达式：AWK 中第
i个字段必须通过$i取得，应明确写成transposed[i] = $i，否则未定义变量产生的空值可能掩盖笔误。- 所有行都执行
transposed[i] = transposed[i] OFS $i：第一行前也会拼接OFS，输出变成以空格开头。- 在
END中循环到NR：样例R = 3、C = 2，会错误输出 3 行，其中最后一行为空；输出数量应是列数。- 在
END中直接依赖最后一行的NF：题目虽保证矩形，但保存columns能固定状态含义，也便于发现或处理扩展场景中的不规则行。- 使用
for (i in transposed)输出：关联数组遍历顺序未定义，列顺序可能变成2,1。- 用
cut -c按字符位置切列：字段长度不固定，alice、21等无法靠固定字符宽度正确转置。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 192. 统计词频 | 中等 | 使用 awk、sort、uniq 重组与聚合文本字段 |
| 193. 有效电话号码 | 简单 | 用正则逐行筛选完整记录 |
| 195. 第十行 | 简单 | 只保留指定行，不需要缓存整个文件 |