Easy

题目描述

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

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

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

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

示例 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]]

提示：

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

解题思路

本题的核心思路是将二维矩阵映射到一维索引，然后重新映射回新的二维矩阵。

解题分析：

首先需要验证重塑操作的合法性：原矩阵的总元素个数必须等于目标矩阵的总元素个数，即 m * n == r * c。如果不相等，直接返回原矩阵。

核心算法：

  1. 一维化索引：将二维坐标 (i, j) 映射为一维索引 index = i * n + j
  2. 逆向映射：将一维索引 index 映射回新的二维坐标 (index / c, index % c)

具体实现方法：

  • 方法一（推荐）：使用一维索引转换，遍历原矩阵的每个元素，计算其在新矩阵中的位置
  • 方法二：先将矩阵拉平为一维数组，再重新构建二维矩阵
  • 方法三：直接按行遍历原矩阵，依次填充新矩阵

推荐使用方法一，因为它空间效率最高，不需要额外的一维数组存储。

代码实现

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m = mat.size();
        int n = mat[0].size();
        
        // 检查重塑操作是否合法
        if (m * n != r * c) {
            return mat;
        }
        
        vector<vector<int>> result(r, vector<int>(c));
        
        // 遍历原矩阵的每个元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 计算一维索引
                int index = i * n + j;
                // 映射到新矩阵的坐标
                int newRow = index / c;
                int newCol = index % c;
                result[newRow][newCol] = mat[i][j];
            }
        }
        
        return result;
    }
};

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
        
        result = [[0] * c for _ in range(r)]
        
        # 遍历原矩阵的每个元素
        for i in range(m):
            for j in range(n):
                # 计算一维索引
                index = i * n + j
                # 映射到新矩阵的坐标
                new_row = index // c
                new_col = index % c
                result[new_row][new_col] = mat[i][j]
        
        return result

public class Solution {
    public int[][] MatrixReshape(int[][] mat, int r, int c) {
        int m = mat.Length;
        int n = mat[0].Length;
        
        // 检查重塑操作是否合法
        if (m * n != r * c) {
            return mat;
        }
        
        int[][] result = new int[r][];
        for (int i = 0; i < r; i++) {
            result[i] = new int[c];
        }
        
        // 遍历原矩阵的每个元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 计算一维索引
                int index = i * n + j;
                // 映射到新矩阵的坐标
                int newRow = index / c;
                int newCol = index % c;
                result[newRow][newCol] = mat[i][j];
            }
        }
        
        return result;
    }
}

var matrixReshape = function(mat, r, c) {
    const m = mat.length;
    const n = mat[0].length;
    
    // 检查重塑操作是否合法
    if (m * n !== r * c) {
        return mat;
    }
    
    const result = Array(r).fill().map(() => Array(c).fill(0));
    
    // 遍历原矩阵的每个元素
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // 计算一维索引
            const index = i * n + j;
            // 映射到新矩阵的坐标
            const newRow = Math.floor(index / c);
            const newCol = index % c;
            result[newRow][newCol] = mat[i][j];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m × n)需要遍历原矩阵的每个元素一次
空间复杂度O(r × c)需要创建新的结果矩阵，不计算返回值的话为 O(1)

相关题目