🍗[LeetCode]Ar566. 重塑矩阵 【矩阵和一维数组下标映射关系】

🚩传送门：https://leetcode-cn.com/problems/reshape-the-matrix/

🍗鸡腿知识点：

1. 数组下标的映射公式

1. 一步转换原因：

👉 一维 x 做中间值 👈

题目

在 MATLAB 中，有一个非常有用的函数 ，它可以将一个 矩阵重塑为另一个大小不同（）的新矩阵，但保留其原始数据。给你一个由二维数组 mat 表示的 矩阵，以及两个正整数 和 ，分别表示想要的重构的矩阵的 行数 和 列数 。重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。如果具有给定参数的 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1：

输入：mat = [[1,2],[3,4]], r = 1, c = 4 输出：[[1,2,3,4]]

示例 2：

输入：mat = [[1,2],[3,4]], r = 2, c = 4 输出：[[1,2],[3,4]]

解题思路：二维数组的一维表示

对于一个行数为 ，列数为 ，行列下标都从 开始编号的二维数组，我们可以通过下面的方式，将其中的每个元素 映射到整数域内，并且它们按照行优先的顺序一一对应着 中的每一个整数。形象化地来说，我们把这个二维数组「排扁」成了一个一维数组。如果读者对机器学习有一定了解，可以知道这就是 操作。

这样的映射即为：

同样地，我们可以将整数 映射回其在矩阵中的下标，即

其中 / 表示整数除法，% 表示取模运算。

那么对于题目需要我们做的事情相当于：

1. 将二维数组 映射成一个一维数组；
2. 将这个一维数组映射回 行 列的二维数组。

当然可以直接用一个一维数组进行过渡，但也可以直接从二维数组 得到 行 列的重塑矩阵：

1. 设 本身为 行 列，如果 ，那么二者包含的元素个数不相同，因此无法进行重塑；
2. 对于 ，第 个元素在 中对应的下标为 ，而在新的重塑矩阵中对应的下标为 。我们直接进行赋值即可。

复杂度分析

时间复杂度：

这里的时间复杂度是在重塑矩阵成功的前提下的时间复杂度，否则当 时，C++ 语言中返回的是原数组的一份拷贝，本质上需要的时间复杂度为，而其余语言可以直接返回原数组的对象，需要的时间复杂度仅为 。

空间复杂度：

这里的空间复杂度不包含返回的重塑矩阵需要的空间。

官方代码

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        //1.行数
        int m = nums.length;
        //2.列数
        int n = nums[0].length;
        //3.能否转换判断
        if (m * n != r * c) {
            return nums;
        }
        int[][] ans = new int[r][c];
        //4.下标映射
        for (int x = 0; x < m * n; ++x) {
            ans[x / c][x % c] = nums[x / n][x % n];
        }
        return ans;
    }
}