LeetCode 566. 重塑矩阵
题目描述
题意分析
将原矩阵按行从左到右、从上到下读取，按相同顺序填入
r行c列的新矩阵。元素不能增加或丢失，因此只有两边总元素数相等时才能重塑，否则按题意返回原矩阵。可以把行优先顺序想成一条编号从零开始的序列。无需真的建立中间一维数组，只要把同一个编号分别换算成旧、新矩阵坐标，就能直接复制。
解法：线性下标映射
核心思路
[!blue]
同一个线性编号分别换算源坐标和目标坐标。 原矩阵有m行、n列，一行占据连续的n个编号。对编号idx，整除n得到它之前有多少个完整行，取模n得到它在当前行内的位置，因此源坐标为(idx/n, idx%n)。目标矩阵每行有c个元素，同理得到目标坐标(idx/c, idx%c)。先确认
m*n == r*c，再枚举0到m*n-1的所有编号。整除和取模会把每个编号唯一地映射到一个格子；两边总数相等，源、目标坐标都在有效范围内，因此每个源元素被复制一次，每个目标格子也恰好填入一次。读取和写入使用相同的
idx，改变的只是每隔多少个元素换一行，元素的行优先顺序不会变化。总数不相等时在分配结果前就返回原矩阵，不会产生只填了一部分的结果。
解题步骤
- 比较旧矩阵与目标矩阵的元素总数。
- 不相等则直接返回原矩阵。
- 创建目标形状，枚举所有线性编号并完成对应复制。
代码实现
class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
int m = mat.length;
int n = mat[0].length;
// 元素总数不等就无法重塑，按题意原样返回。
if ((long) m * n != (long) r * c) {
return mat;
}
int[][] res = new int[r][c];
for (int idx = 0; idx < m * n; idx++) {
// 同一行优先编号，分别用源列数和目标列数还原坐标。
res[idx / c][idx % c] = mat[idx / n][idx % n];
}
return res;
}
}
func matrixReshape(mat [][]int, r int, c int) [][]int {
m, n := len(mat), len(mat[0])
// 元素总数不等就无法重塑，按题意原样返回。
if int64(m)*int64(n) != int64(r)*int64(c) {
return mat
}
res := make([][]int, r)
for i := range res {
res[i] = make([]int, c)
}
for idx := 0; idx < m*n; idx++ {
// 同一行优先编号，分别用源列数和目标列数还原坐标。
res[idx/c][idx%c] = mat[idx/n][idx%n]
}
return res
}
复杂度分析
- 时间复杂度：合法重塑为 $O(mn)$，不合法时直接判断返回。
- 空间复杂度：辅助空间 $O(1)$，新结果矩阵占 $O(rc)$。
关键点总结
[!green]
- 除数和模数使用对应矩阵自己的列数。
- 合法条件是总数相等，不是行列分别相等。
- 不合法时保持原结果，不进行部分复制。
易错点总结
[!yellow]
- 读取源坐标也使用目标列数：读错位置或越界。
- 目标数组仍按旧形状创建：目标坐标可能无法写入。
- 只比较行数或列数：可能拒绝合法重塑。
- 不检查总数就复制：出现空缺位置或写入越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2022. 将一维数组转变成二维数组 | 简单 | 都用线性编号的整除、取模换算行列坐标；本题从二维重塑，原题从一维构造二维。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！