LeetCode 867. 转置矩阵
目录
题目描述
题意分析
给一个 $m$ 行 $n$ 列的二维数组，要返回它沿主对角线翻转后的结果：原来第 $i$ 行第 $j$ 列的元素，翻转后落在第 $j$ 行第 $i$ 列。
最需要注意的信号是「矩阵不保证是方阵」。转置会把 $m \times n$ 变成 $n \times m$，形状本身发生了改变。这意味着结果矩阵必须新开，行数取原来的列数，列数取原来的行数——这一点是整道题唯一的坑，绝大多数错误都出在把 $m$ 和 $n$ 用反上。
题目要求返回新矩阵而不是修改入参，所以不必纠结原地算法。反过来，如果面试官追问「能不能原地」，答案是只有方阵才行，非方阵在同一块连续内存里根本装不下形状变了的结果。
规模上 $m, n$ 都不超过 1000，元素个数不超过 $10^5$，一次线性遍历绰绰有余，不存在任何性能上的取舍。
边界方面题目已经保证 $m, n \ge 1$，不会出现空矩阵；但单行 $1 \times n$ 和单列 $m \times 1$ 这两种极端形状最容易暴露维度写反的 bug，自测时应该优先拿它们试。
解法：直接转置
核心思路
这道题没有可优化的暴力：所有 $mn$ 个元素每个都要被搬运一次，读一次写一次，$O(mn)$ 就是信息论下界。所以真正要想清楚的不是「怎么更快」，而是「下标该怎么映射、结果该开多大」。
把矩阵看成一个从坐标到值的函数 $M(i, j)$，转置操作定义的就是一个新函数 $T(j, i) = M(i, j)$。定义域也随之交换：原来 $i \in [0, m)$、$j \in [0, n)$，新矩阵的第一维取值范围变成 $[0, n)$，第二维变成 $[0, m)$。所以结果矩阵的形状是 $n \times m$，这是唯一需要动脑的一步。
于是维护的不变量非常直接：外层遍历完第 $i$ 行、内层走到第 $j$ 列时，
res中所有满足「列下标小于 $i$，或者列下标等于 $i$ 且行下标小于 $j$」的位置都已经被正确填好，且填的值就是matrix中对应转置位置的值。遍历一结束，res的每个格子都被恰好写过一次，函数关系 $T(j,i) = M(i,j)$ 处处成立。之所以敢用任意遍历顺序（按原矩阵行序、列序，甚至乱序都行），是因为读的是
matrix、写的是res，两块内存互不重叠，不存在「还没读就被覆盖」的问题。这也正是原地转置难写的原因：一旦读写同一块内存，就必须保证每对元素只交换一次。
解题步骤
- 读出原矩阵的行数 $m$ 和列数 $n$。为什么要显式取两个量：后面分配结果矩阵时它们的角色是互换的，取名清楚能大幅降低写反的概率。
- 分配结果矩阵，形状是 $n$ 行 $m$ 列。为什么是 $n$ 行：新矩阵的行下标来自原矩阵的列下标，取值范围是 $[0, n)$。Go 里还要为每一行单独
make出长度为 $m$ 的切片，因为二维切片是「切片的切片」，外层分配完内层仍是nil。- 双重循环遍历原矩阵的每个位置 $(i, j)$，执行
res[j][i] = matrix[i][j]。为什么下标是这个顺序：赋值语句左边是新坐标、右边是旧坐标，把「行列互换」直接翻译过来即可，不需要任何额外推导。- 为什么循环边界仍然按原矩阵的 $m$ 和 $n$ 来写：这样保证每个源元素被读到恰好一次，而写入端由映射的双射性自动保证覆盖完整，比按新矩阵形状去枚举再反查更不容易出错。
- 返回结果矩阵。全程不修改入参，因此调用方持有的原矩阵仍然完好。
- 以
matrix = [[1,2,3],[4,5,6]]走一遍：$m = 2$，$n = 3$，分配出 3 行 2 列的res，初始全为 0。$i=0$ 这一行：$j=0$ 时res[0][0] = matrix[0][0] = 1；$j=1$ 时res[1][0] = matrix[0][1] = 2；$j=2$ 时res[2][0] = matrix[0][2] = 3。此刻res = [[1,0],[2,0],[3,0]]，第一列已填满。$i=1$ 这一行：$j=0$ 时res[0][1] = matrix[1][0] = 4；$j=1$ 时res[1][1] = matrix[1][1] = 5；$j=2$ 时res[2][1] = matrix[1][2] = 6。此刻res = [[1,4],[2,5],[3,6]]，六个格子各被写过一次。返回[[1,4],[2,5],[3,6]]，形状确实从 $2 \times 3$ 变成了 $3 \times 2$。
代码实现
// 满足 res[j][i] = matrix[i][j]。
class Solution {
public int[][] transpose(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] res = new int[n][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res[j][i] = matrix[i][j];
}
}
return res;
}
}
// 满足 res[j][i] = matrix[i][j]。
func transpose(matrix [][]int) [][]int {
m := len(matrix)
n := len(matrix[0])
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, m)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
res[j][i] = matrix[i][j]
}
}
return res
}
复杂度分析
- 时间复杂度：$O(mn)$，其中 $m$、$n$ 分别是原矩阵的行数和列数。每个元素被读一次、写一次，双重循环共执行 $mn$ 轮，每轮都是常数级的下标计算与赋值，没有任何重复访问。
- 空间复杂度：$O(mn)$，用于存放新的 $n \times m$ 结果矩阵。如果按「不计返回值」的口径统计，则额外空间是 $O(1)$，只有几个循环变量。
关键点总结
- 转置是少数会改变数据形状的矩阵操作，$m \times n$ 变 $n \times m$。凡是形状变化的操作，第一步永远是先把结果容器按新形状分配对，再谈搬运。
- 读写分属两块内存时，遍历顺序完全自由；一旦要原地操作，就必须保证每对元素只被交换一次。方阵原地转置的正确写法是内层循环从
j = i + 1开始，只走严格上三角。- 非方阵无法原地转置。这不是实现技巧的问题，而是结果的形状根本不同，面试里被问到时要直接给出这个理由。
- 大矩阵下这个写法的访存模式是「按行连续读、按列跳跃写」，缓存不友好。如果面试官往性能方向追问，可以提分块转置：按 $32 \times 32$ 的小块搬运，让读写两端都落在缓存行内。
- 面试视角：这类题考的是下标推导的严谨度和边界意识。主动拿 $1 \times n$ 和 $m \times 1$ 两个退化形状口头验一遍，比写完就说「done」更有说服力。
易错点总结
- 错误写法：结果矩阵分配成
new int[m][n]。用例matrix = [[1,2,3],[4,5,6]]里 $m=2$、$n=3$，写res[2][0]时第一维越界，直接抛数组下标异常。- 错误写法：赋值写成
res[i][j] = matrix[j][i]，循环边界却仍按 $m$、$n$。非方阵上会越界；方阵上虽然不崩，但读的是未定义的对角另一侧，结果错乱。- 错误写法：Go 里只写了
res := make([][]int, n)就开始赋值。外层切片的每个元素此时还是nil，对res[0][0]赋值会 panic，必须逐行make。- 错误写法：把行数写成
matrix[0].length、列数写成matrix.length。两个维度整体互换后，$1 \times 5$ 的输入会被当成 $5 \times 1$ 处理，循环第一轮就越界。- 错误写法：试图在入参上原地交换
matrix[i][j]和matrix[j][i]。非方阵根本没有matrix[j][i]这个位置；方阵上如果内层循环从j = 0开始，每对元素会被交换两次，等于什么都没做。- 错误写法：把转置当成旋转 90 度。用例
[[1,2],[3,4]]转置的结果是[[1,3],[2,4]]，而顺时针旋转 90 度应得[[3,1],[4,2]]，两者相差一次左右翻转。- 错误写法：先把原矩阵按行拍平成一维再按 $n$ 个一组重组。这做的是重塑形状而不是转置，
[[1,2,3],[4,5,6]]会得到[[1,2],[3,4],[5,6]]，元素位置全错。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 48. 旋转图像 | 中等 | 要求严格原地，做法是「先转置再左右翻转」，考点是原地交换的顺序和只遍历上三角 |
| 566. 重塑矩阵 | 简单 | 同样改变形状但保持行优先的线性次序，考点是一维序号与二维下标之间的整除取余换算 |
| 54. 螺旋矩阵 | 中等 | 输出顺序不是简单的下标映射，需要维护四条边界并按圈收缩，考点从下标推导变成了循环控制 |