[数据结构与算法]【数据结构入门_数组】 Leetcode 566. 重塑矩阵

原题连接：Leetcode 566. Reshape the Matrix

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

Example 2:

Input: mat = [[1,2],[3,4]], r = 2, c = 4
Output: [[1,2],[3,4]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• -1000 <= mat[i][j] <= 1000
• 1 <= r, c <= 300

做法一：直接转换

思路：

对于一个mn的矩阵中的元素，按照从左到右，从上向下进行编号，那么对于编号为x的元素来说，
他在原来矩阵的下标为：A[x / n][x % n]，转换为rc的矩阵后，它的下标为：B[x / c][x % c]
按照这个映射规则进行映射即可。
注意定义结果数组的时候需要初始化，否则不能按下标填数

c++代码：

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        // 原始矩阵为m行n列
        int m = mat.size();
        int n = mat[0].size();

        // 如果n*m 和 r*c不等 就不能进行转换
        if(n * m != r * c)
            return mat;

        // 需要进行初始化ans为r行c列
        vector<vector<int>> ans(r, vector<int>(c));
        for(int i = 0; i < n * m; i++ ){
            ans[i / c][i % c] = mat[i / n][i % n];
        }
        return ans;
    }
};

复杂度分析：

• 时间复杂度：O(m*n)，需要遍历每个元素
• 空间复杂度：O(1)，返回值不计入复杂度