重塑矩阵 图解题解

这道题到底在问什么

输入

mat=[[1,2],[3,4]], r=1, c=4

输出

[[1,2,3,4]]　元素总数都是 4,能重塑

输入

mat=[[1,2],[3,4]], r=2, c=4

输出

[[1,2],[3,4]]　4 ≠ 8,塞不下,原样返回

先想最直接的笨办法

搭一个 4 行 2 列的空架子,圆点表示还没填。等下把刚才那条序列,一个一个按行序填进来。（动画第 15 步）

最优解：一步一步想明白

1. 3记住这把尺子:同一条直线序列,用 n 算旧坐标、用 c 算新坐标。下面每一帧都在套它。
2. 4m=2 行,n=4 列,要重塑成 r=4 行、c=2 列这是原矩阵,2 行 4 列,一共 8 个数。目标是把它们重新装成 4 行 2 列。
3. 5m×n = 2×4 = 8,r×c = 4×2 = 8,相等,可以重塑动手前先算总数。原矩阵 2×4 是 8 个,目标 4×2 也是 8 个,正好装得下,可以重塑。要是总数对不上,后面会演,直接把原矩阵还回去。
4. 6编号 k=0,旧坐标 = (0 整除 4, 0 取余 4) = (0,0),值 1展平就是从左上角出发,一行读完再读下一行。先读 (0,0) 这一格,值是 1,把它放到序列第一位。
5. 7编号 k=1,旧坐标 = (1 整除 4, 1 取余 4) = (0,1),值 2继续沿着这一行往右走,读 (0,1) 的 2,接进序列,现在序列里有 2 个数了。
6. 8编号 k=2,旧坐标 = (2 整除 4, 2 取余 4) = (0,2),值 3继续沿着这一行往右走,读 (0,2) 的 3,接进序列,现在序列里有 3 个数了。
7. 9编号 k=3,旧坐标 = (3 整除 4, 3 取余 4) = (0,3),值 4继续沿着这一行往右走,读 (0,3) 的 4,接进序列,现在序列里有 4 个数了。
8. 10编号 k=4,旧坐标 = (4 整除 4, 4 取余 4) = (1,0),值 5这一行读完了,换到下一行的开头 (1,0),值 5 接到序列后面。注意是整行整行地往下走,顺序不能乱。
9. 11编号 k=5,旧坐标 = (5 整除 4, 5 取余 4) = (1,1),值 6继续沿着这一行往右走,读 (1,1) 的 6,接进序列,现在序列里有 6 个数了。
10. 12编号 k=6,旧坐标 = (6 整除 4, 6 取余 4) = (1,2),值 7继续沿着这一行往右走,读 (1,2) 的 7,接进序列,现在序列里有 7 个数了。
11. 13编号 k=7,旧坐标 = (7 整除 4, 7 取余 4) = (1,3),值 8继续沿着这一行往右走,读 (1,3) 的 8,接进序列,现在序列里有 8 个数了。
12. 14行优先序列 = 1, 2, 3, 4, 5, 6, 7, 8整张矩阵读完了,8 个数按行序排成了一条直线。接下来把这条线按 4×2 的新形状重新装回去。
13. 15先开一个 4 行 2 列的空矩阵,等着按序列填搭一个 4 行 2 列的空架子,圆点表示还没填。等下把刚才那条序列,一个一个按行序填进来。
14. 16编号 k=0,新坐标 = (0 整除 2, 0 取余 2) = (0,0),值 1从序列头部拿出第一个数 1,按新宽度 c=2 算位置:0 整除 2 是第 0 行,0 取余 2 是第 0 列,填到 (0,0)。
15. 17编号 k=1,新坐标 = (1 整除 2, 1 取余 2) = (0,1),值 2接着填第 1 个数 2,落在 (0,1)。可以看到序列是怎么被切成一段段、铺进新形状的。
16. 18编号 k=2,新坐标 = (2 整除 2, 2 取余 2) = (1,0),值 3新矩阵这一行也填满了,换行。第 2 个数 3 落到 (1,0),正好是下一行的开头。
17. 19编号 k=3,新坐标 = (3 整除 2, 3 取余 2) = (1,1),值 4接着填第 3 个数 4,落在 (1,1)。可以看到序列是怎么被切成一段段、铺进新形状的。
18. 20编号 k=4,新坐标 = (4 整除 2, 4 取余 2) = (2,0),值 5新矩阵这一行也填满了,换行。第 4 个数 5 落到 (2,0),正好是下一行的开头。
19. 21编号 k=5,新坐标 = (5 整除 2, 5 取余 2) = (2,1),值 6接着填第 5 个数 6,落在 (2,1)。可以看到序列是怎么被切成一段段、铺进新形状的。
20. 22编号 k=6,新坐标 = (6 整除 2, 6 取余 2) = (3,0),值 7新矩阵这一行也填满了,换行。第 6 个数 7 落到 (3,0),正好是下一行的开头。
21. 23编号 k=7,新坐标 = (7 整除 2, 7 取余 2) = (3,1),值 8接着填第 7 个数 8,落在 (3,1)。可以看到序列是怎么被切成一段段、铺进新形状的。
22. 248 个数全部按行序就位,返回这个新矩阵8 个数全填完了。新矩阵每一行是 [1,2]、[3,4]、[5,6]、[7,8],数字顺序和原来一模一样,只是行列变了。这就是重塑的结果。
23. 25m×n = 8,但 r×c = 3×3 = 9,8 ≠ 9再看一个塞不下的情况。还是这张 8 个数的矩阵,如果要重塑成 3×3,那是 9 个格子,数字不够填、总数对不上。
24. 26总数不等,无法重塑,返回原矩阵 mat这种时候不强行重塑,按题目要求把原矩阵原封不动地还回去。所以总数校验一定要放在最前面。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        if m * n != r * c:
            return mat
        ans = [[0] * c for _ in range(r)]
        for i in range(m * n):
            ans[i // c][i % c] = mat[i // n][i % n]
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m = mat.size(), n = mat[0].size();
        if (m * n != r * c) {
            return mat;
        }
        vector<vector<int>> ans(r, vector<int>(c));
        for (int i = 0; i < m * n; ++i) {
            ans[i / c][i % c] = mat[i / n][i % n];
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length, n = mat[0].length;
        if (m * n != r * c) {
            return mat;
        }
        int[][] ans = new int[r][c];
        for (int i = 0; i < m * n; ++i) {
            ans[i / c][i % c] = mat[i / n][i % n];
        }
        return ans;
    }
}

复杂度

面试官可能追问