Transpose Matrix
你会得到一个由整数构成的矩阵，以行列表的形式表示：matrix[i][j] 是第 i 行、第 j 列的值。返回它的转置矩阵：第 i 行、第 j 列的值移到第 j 行、第 i 列，因此每一行都会变成一列。矩阵不一定是方阵：一个 m × n 矩阵会变成一个 n × m 矩阵。
函数
- matrixinteger-2d-array
- m × n 矩阵，表示为由 m 行组成的列表，每行包含 n 个整数
- 返回值integer-2d-array
- n × m 矩阵的转置，表示为由 n 行、每行 m 个整数构成的列表
约束条件
1 ≤ m, n ≤ 1000，其中m = matrix.length，且n = matrix[i].lengthm × n ≤ 5000- 每一行的长度都相同，都是
n。 -1000 ≤ matrix[i][j] ≤ 1000
示例
- 输入
- matrix = [[1, 2, 3], [4, 5, 6]]
- 输出
- [[1, 4], [2, 5], [3, 6]]
- 解释
- 行
[1, 2, 3]成为第一列，[4, 5, 6]成为第二列。按行读取，结果是[1, 4]、[2, 5]、[3, 6]：一个 3 × 2 矩阵。
- 输入
- matrix = [[1, 2], [3, 4]]
- 输出
- [[1, 3], [2, 4]]
- 解释
- 对角线上的值 1 和 4 保持不变。另两个值交换位置：2 从第 0 行第 1 列移到第 1 行第 0 列，3 则反向移动。
进阶
假设矩阵按行依次存储在一个包含 m × n 个值的一维数组中。你能否不使用第二个数组，直接在这个数组中转置一个非方阵？
提示
逐个打开提示，每个都会多透露一点。
如果输入有
m行和n列，答案有多少行和多少列？比较一个值变换前后的位置：第
i行、第j列的值最终会出现在第j行、第i列。创建一个包含
n行的结果，每行有m个值，然后遍历输入中的每个单元格，并将matrix[i][j]复制到result[j][i]。
题解
转置不会进行计算：(i, j) 处的值会移动到 (j, i)。关键在于形状。结果有 n 行，每行长度为 m，因此，非正方形的行列表无法原地转置；你需要创建一个尺寸交换后的新矩阵并填充它。
逐列读取矩阵
思路
答案中的第 j 行就是输入中的第 j 列，按从上到下的顺序读取。对于 [[1, 2, 3], [4, 5, 6]]，第 0 列依次读取 1 和 4，所以答案的第一行是 [1, 4]。
每个值都读取一次并写入一次：时间复杂度为 O(m × n)，结果占用的空间复杂度为 O(m × n)。构建每个新行时，会跨过输入中的每一行，而不是沿着一行读取，这种方式遍历内存更慢。
算法
- 设
m为行数，n为每行的长度。 - 对于从
0到n-1的每一列j，创建一个空列表。 - 对于从
0到m-1的每个i，将matrix[i][j]添加到该列表中。 - 将该列表作为第
j行添加到结果中，并在最后一列处理完后返回结果。
def transpose(matrix):
m, n = len(matrix), len(matrix[0])
result = []
for j in range(n):
# Column j, read top to bottom, becomes row j of the answer.
column = []
for i in range(m):
column.append(matrix[i][j])
result.append(column)
return result通过镜像每个单元格来填充一个新的 n × m 网格
思路
先创建 n × m 的结果矩阵，然后按照输入的存储顺序逐行读取，并将每个值放到镜像位置：result[j][i] = matrix[i][j]。这样做是正确的，因为转置正是交换索引，并将这一操作应用于每个单元格。
每个值只复制一次，因此时间复杂度为 O(m × n)，网格所占的 O(m × n) 空间正好也是输出本来就需要的空间。逐行读取会按照数据的存储顺序访问内存，而且每个结果行只在最终大小确定后分配一次。
算法
- 令
m表示行数，n表示每行的长度。 - 创建
result，包含n行，每行有m个值。 - 对于输入中的每一行
i和每一列j，设置result[j][i] = matrix[i][j]。 - 返回
result。
def transpose(matrix):
m, n = len(matrix), len(matrix[0])
# The answer has n rows of m values each.
result = [[0] * m for _ in range(n)]
for i in range(m):
for j in range(n):
result[j][i] = matrix[i][j]
return result
易错点和边界情况
- 按输入的形状构建结果。对于 2 × 3 的示例，写入
result[2][0]会越界：结果需要有n行，每行长度为m。 - 原地交换
matrix[i][j]和matrix[j][i]。这只适用于m = n的情况，而且只适用于满足j > i的单元格；遍历每个单元格的循环会把每对元素交换两次，最终矩阵保持不变。 - 在 Python 中，
[[0] * m] * n会创建对同一个列表的n个引用，因此写入一个单元格会改动整列。应分别构建每一行。 - 在 C 中，调用方会将
*returnSize读取为结果的行数n，并将(*returnColumnSizes)[j]读取为每行的长度m。
常见问题3
矩阵的转置是什么？
它是通过交换行和列得到的矩阵：第 i 行、第 j 列的值会移动到第 j 行、第 i 列。一个 2 × 3 矩阵会变成 3 × 2，转置两次后会恢复原样。
转置矩阵的时间复杂度是多少？
O(m × n)：m × n 个值中的每一个都只会复制一次，而且要得到答案，至少需要这么多操作。新矩阵占用 O(m × n) 的空间，与输出本身的大小相同。
你能原地转置矩阵吗？
对于方阵，可以：对对角线上方的每个单元格，将 matrix[i][j] 与 matrix[j][i] 交换，额外内存占用为 O(1)。非方阵的形状会发生变化，因此如果使用行列表，就需要创建一个新矩阵。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def transpose(matrix):
# 在这里编写代码测试 #1
测试 #2
参数
matrix = [[1, 2, 3], [4, 5, 6]]
预期输出
[[1, 4], [2, 5], [3, 6]]