0566. Reshape the Matrix¶
题目信息¶
- 题号:
0566
- 难度:
Easy
- 主题:
矩阵重塑、行优先顺序、元素总数、失败回退
- 原题:
- 重点:
新旧矩阵元素总数必须相同、按原矩阵行优先顺序填充、无法重塑时返回原矩阵
题目重述¶
给定 m × n 整数矩阵 mat,以及目标行数 r 和列数 c。若 m * n = r * c,把原矩阵中的元素按从左到右、从上到下的行优先顺序依次填入一个 r × c 新矩阵并返回。
若目标形状容纳的元素数量与原矩阵不同,则不能进行重塑,必须返回原矩阵。重塑只改变行列组织方式,不能丢失、复制或重新排序元素。
自建示例¶
成功改变形状:
输入:mat = [[1,2,3],[4,5,6]],r = 3,c = 2
输出:[[1,2],[3,4],[5,6]]
解释:六个元素按原行优先顺序依次填入 3 行 2 列矩阵。
元素数量不匹配:
输入:mat = [[1,2],[3,4]],r = 1,c = 3
输出:[[1,2],[3,4]]
解释:原矩阵有 4 个元素,目标只有 3 个位置,因此返回原矩阵。
用一维序号保持行优先顺序¶
先比较原矩阵和目标矩阵的元素总数;不相等时直接返回原矩阵。相等时把原坐标 (i,j) 映射为一维序号 i * oldColumns + j,再映射到目标的 (index / c, index % c),从而只改变形状不改变顺序。
C++ 实现¶
class Solution {
public:
std::vector<std::vector<int>> matrixReshape(
std::vector<std::vector<int>>& mat, int r, int c) {
int rows = static_cast<int>(mat.size());
int columns = static_cast<int>(mat[0].size());
if (static_cast<long long>(rows) * columns !=
static_cast<long long>(r) * c) {
return mat;
}
std::vector<std::vector<int>> result(
r, std::vector<int>(c));
for (int index = 0; index < rows * columns; ++index) {
int oldRow = index / columns;
int oldColumn = index % columns;
result[index / c][index % c] = mat[oldRow][oldColumn];
}
return result;
}
};
代码分析¶
一维序号在新旧矩阵中保持不变,保证每个元素恰好复制一次且顺序不变;容量检查失败时不创建新结构。时间复杂度为 O(rows * columns),结果矩阵空间为 O(r*c)。