LeetCode 566. 重塑矩阵

2021-08-21 HGNULB 约 8 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 566. 重塑矩阵

题意分析

给一个 m × n 的矩阵 mat 和两个整数 r、c，要求把它「重塑」成 r × c 的新矩阵。重塑的唯一规则是：把原矩阵按行优先的顺序（第一行从左到右、然后第二行……）读成一串数，再按同样的行优先顺序填进新矩阵。如果重塑不合法，原样返回 mat。

「行优先顺序不变」这一句是全部题意。它意味着重塑并不改变元素之间的先后次序，只改变「每行放几个」这个分行方式——就像把一段文字换个宽度重新排版，字还是那些字、顺序还是那个顺序，只是换行的位置变了。想清楚这一点，题目就从「二维搬运」降维成了「一维重新分段」。

合法性判据也就随之明确：新矩阵能装下的元素数是 $r \cdot c$，原矩阵有 $m \cdot n$ 个，两者必须完全相等。少了会有空格子没填，多了会装不下。不等就直接返回 mat，不需要报错也不需要部分填充。

数据规模是标准的二维线性量级，显然目标就是每个元素只搬一次的 $O(mn)$。题目本身不含任何算法难点，考的是坐标换算的准确性——这是矩阵类题目的基本功，也是面试官用来看代码是否严谨的观察点。

边界：m * n 与 r * c 相乘可能超出 int 范围吗？本题规模很小不会，但形成「乘法先想溢出」的习惯没有坏处。另外原矩阵至少有一行一列，所以 mat[0].length 是安全的；不合法时返回的是原数组本身而不是拷贝，题目允许这样做。

解法：线性下标映射

核心思路

最直白的写法是开两组行列指针：一组走原矩阵、一组走新矩阵，每搬一个元素就手动推进两组指针，某个指针的列号走到头就换行、行号清零。这样能做对，但要维护四个互相牵制的变量、写两处「越界就进位」的判断，容易漏也容易乱。

换个角度：既然重塑本质上是「拉成一维再重新分段」，那就让一维下标成为唯一的真相来源，两边的二维坐标都从它换算出来，不用各自维护。

一个 p 列的矩阵，其行优先编号与二维坐标之间的换算是固定的一对公式：坐标 (x, y) 对应编号 idx = x * p + y；反过来，编号 idx 对应 x = idx / p、y = idx % p。除法给出「走完了几整行」，取模给出「在当前行走了多远」——这就是全部原理。

直接枚举行优先序号 idx = 0..m*n-1。它在原矩阵中的坐标是 (idx / n, idx % n)，在新矩阵中的坐标是 (idx / c, idx % c)，因此搬运式就是 res[idx/c][idx%c] = mat[idx/n][idx%n]。

循环不变量是：处理 idx 前，行优先序列中编号小于 idx 的元素已经按原顺序落入结果，编号不小于 idx 的元素尚未写入。当前赋值复制同一个线性序号，因而把不变量推进一格；循环结束后所有元素恰好复制一次。

特别注意两侧使用不同列数：还原源坐标用原列数 n，还原目标坐标用新列数 c。把两者混用会读错元素或直接越界。

合法性检查必须放在最前面：m * n != r * c 时直接返回 mat，之后的代码就可以在「总数相等」的前提下无脑执行，idx 绝不会超出新矩阵的范围。

解题步骤

取出 m = mat.length、n = mat[0].length：n 用于把线性序号还原成源矩阵坐标；题目保证矩阵非空。

若 m * n != r * c，直接返回 mat。为什么：这是题目规定的唯一非法情形，提前返回后主循环就可以假定「总数刚好对得上」，从而不需要任何越界保护。返回原数组而不是拷贝，符合题目「返回原始矩阵」的措辞。

新建 r × c 的结果矩阵 res。为什么：题目要求返回新矩阵而不是就地修改；行列数用目标值而不是原值，这是显而易见但也确实有人写反的地方。

枚举 idx 从 0 到 m*n-1，让它成为源矩阵和目标矩阵共享的行优先序号。

读取 mat[idx / n][idx % n]：按原矩阵列数 n 把序号还原成源坐标。

写入 res[idx / c][idx % c]：按目标列数 c 把同一序号还原成目标坐标。

返回 res。

以 mat = [[1, 2], [3, 4]], r = 1, c = 4 走一遍。m = 2、n = 2，m * n = 4 等于 r * c = 4，合法。新建 1 × 4 的 res。

(0,0)：idx = 0 * 2 + 0 = 0，落点 (0 / 4, 0 % 4) = (0, 0)，写入 1。

(0,1)：idx = 0 * 2 + 1 = 1，落点 (0, 1)，写入 2。

(1,0)：idx = 1 * 2 + 0 = 2，落点 (0, 2)，写入 3。

(1,1)：idx = 1 * 2 + 1 = 3，落点 (0, 3)，写入 4。

返回 [[1, 2, 3, 4]]。注意 (1,0) 这一步：它在原矩阵里是「第二行第一个」，但在一维序列里是第 3 个（下标 2），在新矩阵里落到了第一行第三列——原矩阵的换行位置完全被忽略了，只有一维序号说了算，这正是「拉直再分段」的含义。

再看 mat = [[1,2,3,4]], r = 2, c = 2。当 idx = 2 时，源坐标是 (2/4, 2%4) = (0,2)，读到 3；目标坐标是 (2/2, 2%2) = (1,0)，把 3 放到第二行第一列。若源坐标也误用 c=2，会访问不存在的 mat[1][0]。

代码实现

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(m \cdot n)$，每个线性序号只复制一次。

空间复杂度：$O(r \cdot c)$，即 $O(m \cdot n)$。凭什么：唯一的额外分配是结果矩阵本身，大小固定为 $r \cdot c$；除此之外只有 m、n、i、j、idx 几个标量。若把结果矩阵视为必须的输出而不计入辅助空间，则辅助空间是 $O(1)$——面试时把这两种口径都说清楚更稳妥。

关键点总结

二维到二维的「重新分行」问题，统一的解法是降到一维做中转。两边的二维坐标都从同一个一维序号换算，天生不可能错位，比维护两组行列指针可靠得多。

行优先编号的两个公式要背成肌肉记忆：idx = 行号 × 列数 + 列号，反解 行号 = idx / 列数、列号 = idx % 列数。注意这里的「列数」永远是该矩阵自己的列数。

同一个 idx 还原源坐标时用 n，还原目标坐标时用 c；两个列数不能混用。

合法性检查提前返回，让主循环运行在「前提已满足」的干净环境里，从而不必写任何越界保护——这是把边界处理集中在入口的通用手法。

面试表达只需抓住两点：先校验元素总数，再用同一个线性序号分别还原源坐标和目标坐标。

易错点总结

读取源坐标时用了目标列数 c：mat = [[1,2],[3,4]], r = 4, c = 1 时 idx=1 会读 mat[1][0] 得到 3，而正确的第二个元素是 mat[0][1]=2。

计算目标坐标时用了原列数 n：mat = [[1,2,3,4]], r = 2, c = 2 时 idx % 4 可达 3，而结果只有两列，直接越界。

忘记合法性检查：mat = [[1,2],[3,4]], r = 2, c = 3 → idx 最大为 3，而新矩阵有 6 个位置，返回的矩阵里有两个位置是默认的 0；反过来若 r * c 更小则直接数组越界。

合法性检查写成 m != r || n != c：mat = [[1,2],[3,4]], r = 1, c = 4 → 被误判为非法，直接返回原矩阵，而这个重塑本来是合法的。

不合法时返回 null 或空矩阵：判题期望原样返回 mat → 返回值类型对但内容不符，直接判错。

新矩阵开成 new int[m][n]：r、c 与 m、n 不同时 → 写入 res[idx / c] 时行号可能超过 m，抛越界异常。

idx / c 与 idx % c 写反：mat = [[1,2],[3,4]], r = 4, c = 1 → 行列互换，idx = 2 时落到 res[0][2]，列号超出仅有的 1 列，越界。

用两组指针手动推进却漏了换行清零：新矩阵的列指针走到 c 后只加行号不把列号归零 → 第二行第一次写入就落在 res[1][c]，越界。

就地修改 mat 而不新建结果：r、c 与原形状不同时根本无法就地完成 → 编译不过或结构错乱；即使形状相同，原地覆盖也会破坏尚未读取的元素。

相似题目

题目	难度	考察点
867. 转置矩阵	简单	同为坐标映射，但换的是行列身份（`res[j][i] = mat[i][j]`）而非分段方式
48. 旋转图像	中等	要求原地完成，靠「转置 + 翻转」或四元素循环交换，不能借助新矩阵
54. 螺旋矩阵	中等	输出顺序不再是行优先，需要用四条边界逐层收缩来控制遍历路径
59. 螺旋矩阵 II	中等	与 54 互为逆向，按螺旋顺序往空矩阵里填数，考的是同一套边界收缩
498. 对角线遍历	中等	遍历顺序沿对角线折返，需要按 `i + j` 的奇偶决定方向并处理四类边界
74. 搜索二维矩阵	中等	同样把矩阵看作一维序列，但目的是在其上做二分查找而非搬运
73. 矩阵置零	中等	难点在原地标记，用首行首列当标记位以达到 $O(1)$ 额外空间
289. 生命游戏	中等	需要原地同时更新所有格子，靠位编码把新旧两个状态存在同一个整数里