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

** 题解一： 一行一行的旋转 **
题解思路： 声明一个额外的数组ans,将ans保存旋转之后的数组。
位置摆放分析：
对于一个3阶矩阵-> 旋转90度之后坐标变换（(0,0)--->(0,2)；(0,1)-->(1,1) ; (0,2)--->(2,2)...） 所以 ans[j][n-1-i] = ans[i][j];
** 复杂度分析：**
时间复制度：O(N^2)
空间复杂度：O(N^2)
实现如下：

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-1-i] = mat[i][j];  // 摆放位置
          }
      }
      return ans;
    }
};

题解二：原地旋转
分析：有题解一得出的关系式mat[j][n-1-i] = mat[i][j];

使用一个临时变量保存mat[j][n-1-i]的值，完成原地交换。
当n为偶数，需要枚举(n^2)/4个位置，当n为奇数，需要枚举(n^2-1)/4个位置。

复杂度分析：
时间复杂度：O(N^2)
空间复杂度：O(1)
实现如下:

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        for(int i = 0; i<n/2;i++) //  行
        {
            for(int j = 0; j<(n+1)/2;j++)  //列
            {
                int tmp = mat[j][n-1-i]; // 临时变量保存mat[j][n-1-i]
                // 进行4次交换
                mat[j][n-1-i] = mat[i][j];
                mat[i][j] = mat[n-1-j][i];
                mat[n-1-j][i] = mat[n-1-i][n-1-j];
                mat[n-1-i][n-1-j] = tmp;
            }
        }
       return mat;     
    }
};

题解三：两次交换
分析如图：


复杂度分析：
时间复杂度：O(N^2)
空间复杂度：O(1)

实现如下：

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        //上下对称交换
        for(int i = 0; i<n/2;i++){
            for(int j = 0;j<n;j++){
                swap(mat[i][j], mat[n-i-1][j]);
            }
        }
        //主对角线交换
        for(int i = 0;i<n;i++){
            for(int j = i+1;j<n;j++){
                swap(mat[i][j], mat[j][i]);
            }
        }
        return mat;
    }
};