LeetCode48 Rotate Image

By | 11/03/2018

【题目】:

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOTallocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

[Code]:

#include<iostream>

#include<vector>

using namespace std;

//顺时针旋转90度可以转变成为先对矩阵进行上下翻转然后再沿左上到右下的对角线翻转

class Solution {

public:

    void rotate(vector<vector<int> >& matrix) {

        int m = matrix.size();

        int n = matrix[0].size();

        if(m == 0){

            return;

        }

        //上下反转

        for(int i = 0; i < m/2; i++){

            for(int j = 0; j < n; j++){

                int tmp = matrix[i][j];

                matrix[i][j] = matrix[m-i-1][j];

                matrix[m-i-1][j] = tmp;

            }




        }

        //沿对角线对折

        for(int i = 0; i < m; i++){

            for(int j = i; j < n; j++){

                int tmp = matrix[i][j];

                matrix[i][j] = matrix[j][i];

                matrix[j][i] = tmp;

            }

        }

        return;

    }

};




//Better答案

class SolutionB {

public:

    void rotate(vector<vector<int> >& matrix) {

        //应用stl一步改变了上下翻转

        reverse(matrix.begin(), matrix.end());

        for(int i=0;i<matrix.size();i++){

            for(int j=i+1;j<matrix.size();j++){

                swap(matrix[i][j], matrix[j][i]);

            }

        }

    }

};


【遇到的问题及解决办法】:

对于矩阵的变换我们要敏感因为在线性代数当中有讲过对矩阵的变换同时在机器学习当中我们也用到了矩阵因为对于矩阵的操作我们需要敏感,因为之前记得转换的操作所以我就是直接写了想上下翻转然后再从左上到右下的关于这条对角线转换最后得到的结果就是将原矩阵顺时针旋转了90度的结果,但是在这个地方我在查看运行的detail的时候看到了我写的算法并不是最优秀的于是看了一下最优秀的算法的操作,发现其本质跟我的操作是几乎一模一样的只是不一样的在于对于矩阵的上下翻转其是通过标准模版中的vector的成员函数reverse进行操作的,那么一个vec(二维vector)的reverse到底是什么呢?这个地方又设计到了对vector构造的解析了于是乎我又去查了一波发现对于vector< vector<int> >    其是先构造的一维然后将多个一维的当作元素构造在一起那么就是二维了,所以知道了其本质之后其实就很容易知道了vec.reverse()其实是将每一行进行了翻转也就是把我的第一个for循环给解决了,难怪他的速度比我的快(尽管也没有快多少),然后就是关于矩阵的对角线的交换了, 就是横纵坐标的交换,但是中间的不需要进行操作。

 

如果这篇文章对你有帮助,欢迎打赏:

WechatIMG47

发表评论