当前位置：网站首页>[数组]566. 重塑矩阵-简单

[数组]566. 重塑矩阵-简单

2022-07-05 03:36:00 【51CTO】

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

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

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

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

示例 1：

[数组]566. 重塑矩阵-简单_数组

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

输出：[[1,2,3,4]]

示例 2：

[数组]566. 重塑矩阵-简单_数组_02

输入：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

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/reshape-the-matrix

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

思路：

判断输入的矩阵个数和输出矩阵个数是否相等
为输出矩阵申请空间
遍历原始矩阵，将原始矩阵元素搬到输出矩阵

代码如下：

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       class 
       
       Solution
       
{
       
       public:
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       matrixReshape(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       mat, 
       
       int 
       
       r, 
       
       int 
       
       c)
       
  {
       
       if (
       
       mat.
       
       empty())
       
    {
       
       return 
       
       mat;
       
    }
       
       int 
       
       m 
       
       = 
       
       mat.
       
       size();
       
       int 
       
       n 
       
       = 
       
       mat[
       
       0].
       
       size();
       
       if (
       
       m 
       
       * 
       
       n 
       
       != 
       
       r 
       
       * 
       
       c)
       
    {
       
       return 
       
       mat;
       
    }
       
       std::vector
       
       <
       
       std::vector
       
       <
       
       int
       
       >> 
       
       ans(
       
       r, 
       
       std::vector
       
       <
       
       int
       
       >(
       
       c, 
       
       0));
       
       int 
       
       t 
       
       = 
       
       0;
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       m; 
       
       ++
       
       i)
       
    {
       
       for (
       
       int 
       
       k 
       
       = 
       
       0; 
       
       k 
       
       < 
       
       n; 
       
       ++
       
       k)
       
      {
       
       ans[
       
       t 
       
       / 
       
       c][
       
       t 
       
       % 
       
       c] 
       
       = 
       
       mat[
       
       i][
       
       k];
       
       t
       
       ++;
       
      }
       
    }
       
       return 
       
       ans;
       
  }
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.

多数几句

leetcode上下面的运行时间居然比我的还要快(我的12ms)，简直离谱了，先看leetcode给的8ms的代码。

       
       class 
       
       Solution {
       
       public:
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       matrixReshape(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >>& 
       
       mat, 
       
       int 
       
       r, 
       
       int 
       
       c) {
       
       int 
       
       m
       
       =
       
       mat.
       
       size();
       
       int 
       
       n
       
       =
       
       mat[
       
       0].
       
       size();
       
       int 
       
       num
       
       =
       
       0;
       
       vector
       
       <
       
       int
       
       > 
       
       s;
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       mat1(
       
       r,
       
       vector
       
       <
       
       int
       
       >(
       
       c));
       
       //初始化大小了才能赋值
       
       if(
       
       m
       
       *
       
       n
       
       !=
       
       r
       
       *
       
       c)
       
{
       
       return 
       
       mat;
       
}
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       m;
       
       i
       
       ++)
       
{
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       n;
       
       j
       
       ++)
       
   {
       
       s.
       
       push_back(
       
       mat[
       
       i][
       
       j]);
       
   }
       
}
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       r;
       
       i
       
       ++)
       
{
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       c;
       
       j
       
       ++)
       
   {
       
       mat1[
       
       i][
       
       j]
       
       =
       
       s[
       
       num];
       
       num
       
       ++;
       
   }
       
}
       
       return 
       
       mat1;
       
    }
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.

这个代码不仅比我多申请一个vector，而且还有元素的各种push_back，这些都是额外的开销，居然比我的还快，leetcode的时间判断是真的蛋疼。

当然上面我的代码也有可以优化的，我们知道CPU是有缓存的，如果缓存命中率高，那么程序运行的就能更快。如果可以减少计算，那么提高程序的运行效率。我们可以从最后的那个循环入手进行优化，优化后的代码如下：

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       class 
       
       Solution
       
{
       
       public:
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       matrixReshape(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       mat, 
       
       int 
       
       r, 
       
       int 
       
       c)
       
  {
       
       if (
       
       mat.
       
       empty())
       
    {
       
       return 
       
       mat;
       
    }
       
       int 
       
       m 
       
       = 
       
       mat.
       
       size();
       
       int 
       
       n 
       
       = 
       
       mat[
       
       0].
       
       size();
       
       int 
       
       total_count 
       
       = 
       
       m
       
       *
       
       n;
       
       if (
       
       total_count 
       
       != 
       
       r 
       
       * 
       
       c)
       
    {
       
       return 
       
       mat;
       
    }
       
       std::vector
       
       <
       
       std::vector
       
       <
       
       int
       
       >> 
       
       ans(
       
       r, 
       
       std::vector
       
       <
       
       int
       
       >(
       
       c, 
       
       0));
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       total_count; 
       
       ++
       
       i)
       
    {
       
       ans[
       
       i 
       
       / 
       
       c][
       
       i 
       
       % 
       
       c] 
       
       = 
       
       mat[
       
       i
       
       /
       
       n][
       
       i
       
       %
       
       n];
       
       t
       
       ++;
       
    }
       
       return 
       
       ans;
       
  }
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.