力扣(LeetCode)566. 重塑矩阵(C语言)

一、环境说明

1. 本文是 LeetCode 566题 : 重塑矩阵，使用c语言实现。
2. 模拟。
3. 测试环境:Visual Studio 2019。

二、代码展示

//两种做法
//使用一维数组保存原二维矩阵。O(n)空间
//使用小学奥数/线性代数，映射原二维矩阵和新二维矩阵的元素。O(1)空间
int** matrixReshape(int** mat, int matSize, int* matColSize, int r, int c, int* returnSize, int** returnColumnSizes){
    //改变矩阵形状。
    if(r*c!=matSize*(matColSize[0])){//不能改变，输出原矩阵
        *returnSize = matSize;
        *returnColumnSizes = matColSize;
        return mat;
    }
    int **ans = (int**)calloc(r,sizeof(int*));
    returnSize[0] = r;
    returnColumnSizes[0] = (int*)calloc(r,sizeof(int));
    for(int i = 0;i<r;i++){//初始化新矩阵
        returnColumnSizes[0][i] = c;
        ans[i]=(int*)calloc(c,sizeof(int));
    }
    for(int i = 0;i<r*c;i++){//新矩阵赋值
        ans[i/c][i%c] = mat[i/matColSize[0]][i%matColSize[0]];
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、思路分析

• 重塑矩阵，考察矩阵元素位置与列的对应关系。
• 想象一个$m\ast n$的矩阵，按行序，从$0$行到$m-1$行，首位相接放入一维数组$nums$，那么数组大小是$m\ast n$。用$i$表示数组的某个元素，数组和矩阵的映射关系是$matrix[i/column][i\%column]=nums[i]$
• 对于矩阵压缩得到的一维数组，数组的$i$只和矩阵的列$column$对应。
• 同理，我们也可以用矩阵$column$得到对应数组的$i$。
• 利用数组做中间使者，等价一下，两个矩阵也有列和列对应的关系。
• 知道列和列存在对应关系，看代码就行~

四、代码分析

• 理解思路很重要！
• 博主欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:$O(m\ast n)$ ,$mat$数组的大小=$m\ast n$。一次遍历，通过$mat$建立$ans$的时间复杂度是$O(m\ast n)$。
2. 空间复杂度:$O(1)$,不考虑保存答案的矩阵，没有使用额外的线性空间，空间复杂度$O(1)$。