当前位置：网站首页>[array]566 Reshape the matrix - simple

[array]566 Reshape the matrix - simple

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

stay MATLAB in , There's a very useful function reshape , It can put a m x n The matrix is remodeled to another different size （r x c） The new matrix of , But keep its original data .

Give you a two-dimensional array mat It means m x n matrix , And two positive integers r and c , Represent the number of rows and columns of the matrix to be reconstructed respectively .

The reconstructed matrix needs to replace all elements of the original matrix with the same Row traversal order fill .

If the reshape The operation is feasible and reasonable , The new reshaping matrix is output ; otherwise , Output raw matrix .

Example 1：

[ Array ]566. Reshaping the matrix - Simple _ Array

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

Output ：[[1,2,3,4]]

Example 2：

[ Array ]566. Reshaping the matrix - Simple _ Array _02

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

Output ：[[1,2],[3,4]]

Tips ：

m == mat.length

n == mat[i].length

1 <= m, n <= 100

-1000 <= mat[i][j] <= 1000

1 <= r, c <= 300

source ： Power button （LeetCode）

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

Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer key

Ideas ：

Judge whether the number of input matrices and the number of output matrices are equal
Apply for space for the output matrix
Traverse the original matrix , Move the original matrix elements to the output matrix

The code is as follows ：

       
       #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.

A few more sentences

leetcode The running time of the upper and lower parts is even faster than mine ( my 12ms), It's ridiculous , First look at leetcode Given 8ms Code for .

       
       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));
       
       // The value can only be assigned after the initialization size 
       
       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.

This code is not only one more than me vector, And there are all kinds of elements push_back, These are extra expenses , It's faster than mine ,leetcode It's really painful to judge the time .

Of course, my code above can also be optimized , We know CPU There is a cache , If the cache hit rate is high , Then the program can run faster . If you can reduce the calculation , Then improve the efficiency of the program . We can optimize from the last cycle , The optimized code is as follows ：

       
       #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.