题解 | #顺时针旋转矩阵#

解题思路：

• 本题主要在于找出顺时针旋转90°后的矩阵与原矩阵对应位置之间的关系和规律。

方法一：

• 找出整体的规律，并使用一个辅助数组来存储新的矩阵。
  
• 从上图中的矩阵旋转来看：原矩阵元素的列数变成新矩阵元素的行数；原矩阵元素的行数是第2行，旋转后元素的列数是从右往左倒数第2列。因此对于原矩阵mat[i][j]，旋转后该值应该在新矩阵ans[j][n-i-1]的位置。

  class Solution {
  public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
        vector<vector<int>> ans(n,vector<int>(n));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ans[j][n-i-1]=mat[i][j];
            }
        }
        return ans;
    }
  };

  复杂度分析：

  时间复杂度：O(n^2)，矩阵元素数量n^2.
  空间复杂度：O(n^2)，用一个矩阵的空间进行存储。

方法二：

• 方法一使用的O(n^2)的辅助空间相对来说较为浪费，可以使用少量的辅助变量即可实现旋转。方法二的思路是由外而内，一层一层地进行旋转。示意图如下：
  
• 外层的旋转之后始终是在外层，因为只需要一个临时变量即可实现旋转替换。

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
        //由外而内，一层一层地进行变换
        int rotateTimes=n/2;
        int i=0,low=0,high=n-1;
        while(i++<rotateTimes){
            for(int j=0;j<high-low;j++){
                int tmp=mat[low][low+j];
                mat[low][low+j]=mat[high-j][low];
                mat[high-j][low]=mat[high][high-j];
                mat[high][high-j]=mat[low+j][high];
                mat[low+j][high]=tmp;
            }            
            low+=1;
            high-=1;
        }
        return mat;
    }
};

复杂度分析：

时间复杂度：O(n^2)，双重循环。
空间复杂度：O(1)，常数个临时变量。