0194. Transpose File

题目信息

题号:
  1. 转置文件

难度:

Medium

主题:

Shell、awk、文本矩阵、跨行状态

原题:

LeetCode 0194

重点:

将原第 c 列跨行累积为第 c 个输出缓冲,并在读完文件后按列号依次输出

题目重述

编写 Bash 脚本读取 file.txt。文件可视为文本矩阵,每行字段数相同,字段以空白分隔。 输出矩阵转置:原文件第 c 列成为输出第 c 行,同一输出行的字段用单个空格连接, 并保持原行从上到下的顺序。

若输入有 r 行、c 列,输出应有 c 行,每行 r 个字段。

自建示例

file.txt:
item qty zone
pens 8 north
paper 3 west

输出:
item pens paper
qty 8 3
zone north west

Bash 实现

#!/usr/bin/env bash

awk '
NR == 1 {
    columns = NF
}

{
    for (column = 1; column <= NF; ++column) {
        if (NR == 1) {
            transposed[column] = $column
        } else {
            transposed[column] = \
                transposed[column] " " $column
        }
    }
}

END {
    for (column = 1; column <= columns; ++column) {
        print transposed[column]
    }
}
' file.txt

题解

行流与目标输出方向相反

awk 天然一次读入一行,而转置后的第一行需要原文件 每一行 的第一个字段。读到输入 第一行时,任何输出行都还不完整,不能立刻打印;必须把属于同一原始列的字段跨行保存, 等文件读取结束再输出。

可以先统计列数,再对每一列调用一次 cut 或 awk,但文件会被重复扫描 c 次。 主脚本只扫描一遍输入,为每个原始列维护一个不断增长的输出缓冲。

状态如何对应转置定义

NR 是当前输入行号,NF 是当前行字段数,$column 是该行第 column 个字段。 数组 transposed[column] 的不变量是:处理完前 NR 行后,它恰好包含这些行的第 column 个字段,顺序与原行一致,并以单个空格分隔。

处理第一行时直接赋值,不添加前导空格;之后每读一行,就在旧缓冲末尾追加一个空格和当前 字段。这个状态转移把矩阵坐标:

input[row][column]

写入对应的:

output[column] 的下一个字段

因此无需保存完整二维数组或在结束阶段重新访问单元格。

为什么单独记录列数

第一条规则在 NR == 1 时保存 columns = NF。题目保证所有输入行字段数相同,第一行 即可确定最终输出行数。END 阶段使用这个固定值,而不是依赖最后一行的临时 NF, 让状态含义更明确;空文件从未设置 columns,其数值默认为 0,结束循环不会输出任何行。

awk 默认把一段连续空白当作字段分隔,所以输入使用一个或多个空格时,$column 仍是 单独字段。脚本自己拼接字面 " ",保证输出字段之间恰好一个空格,不继承输入中的多余 间隔。

具体状态走读

处理示例第一行后:

transposed[1] = "item"
transposed[2] = "qty"
transposed[3] = "zone"

第二行到来后分别追加 pens、8、north,状态变成 "item pens"、"qty 8"、"zone north";第三行再追加 paper、3、west。直到此时三个输出行才完整,END 按列号 1、2、3 依次打印。

顺序与边界

输入行从上到下读取,追加操作天然保持每个输出行内部字段顺序;END 中列号递增,保持 原列从左到右成为输出行从上到下。关联数组本身的迭代顺序没有保证,所以不能写 for (column in transposed),必须显式使用数值范围 1..columns。

设文件有 r*c 个字段,总字符量为 L。每个字段读取、追加和最终输出一次,概念上 为 O(L) 工作;由于不可在读完整列前输出,脚本保存的列缓冲总长度为 O(L)。它用 内存换取一次文件扫描;逐列多次扫描可降低单次缓冲,但会重复读取输入。