题目描述

在 MATLAB 中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数 r 和 c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

样例

输入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4

输出: 
[[1,2,3,4]]

解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

输入: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4

输出: 
[[1,2],
 [3,4]]

解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。

算法

(模拟) $O(nm)$

1. 比较 n * m 是否等于 r * c，若不等于则说明不可转化，直接返回原矩阵。
2. 否则以行遍历顺序逐一遍历原矩阵，同时按照 每行 c 个的格式填充到新矩阵中即可。

时间复杂度

• 原矩阵的每个位置仅遍历一次，故时间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int n = nums.size(), m = nums[0].size();
        if (n * m != r * c)
            return nums;
        vector<vector<int>> res(r, vector<int>(c));
        int t_i = 0, t_j = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                res[t_i][t_j] = nums[i][j];
                t_j++;
                if (t_j == c) {
                    t_i++;
                    t_j = 0;
                }
            }
        return res;
    }
};