面试金典0107 旋转矩阵

题目：

• 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

  不占用额外内存空间能否做到？

  # 样例1
  给定 matrix = 
  [
    [1,2,3],
    [4,5,6],
    [7,8,9]
  ],
  
  原地旋转输入矩阵，使其变为:
  [
    [7,4,1],
    [8,5,2],
    [9,6,3]
  ]
      
  # 样例2
  给定 matrix =
  [
    [ 5, 1, 9,11],
    [ 2, 4, 8,10],
    [13, 3, 6, 7],
    [15,14,12,16]
  ], 
  
  原地旋转输入矩阵，使其变为:
  [
    [15,13, 2, 5],
    [14, 3, 4, 1],
    [12, 6, 8, 9],
    [16, 7,10,11]
  ]

解题方法：

有旋转时记得用对称性来计算旋转前后的坐标

1. 原地旋转（根据顺时针旋转特性）：旋转前后是点对点的变化，因此只需要将对应的点旋转即可，这里由于不让使用额外空间，因此可以顺时针switch三遍起始点和对应点即可

   时间复杂度为\(O(n^2)\)，额外的空间复杂度为\(O(1)\)

2. 辅助空间（利用多余空间）：新建另一个N × N的矩阵，遍历时交换元素到对应位置

   时间复杂度为\(O(n^2)\)，额外的空间复杂度为\(O(n^2)\)，

解法一：原地旋转

• 如何计算对应位置？
  1. 位置3和1是轴对称，也就是关于横轴对称后再关于纵轴对称，计算相应的节点即可
  2. 位置2和1是先关于纵轴对称后，再关于对角线对称，可以通过计算得到
  3. 位置4和1是先关于横轴对称，然后再关于对角线对称
• 用位运算代替除法，右移1个单位等价于除以二

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if(n == 0) { return; }
        int r = (n>>1)-1; //左上角区域的最大行下标
        int c = (n-1)>>1; //左上角区域的最大列下标，行列下标从 0 开始。
        for(int i = r; i >= 0; --i) {
            for(int j = c; j >= 0; --j) {
                swap(matrix[i][j], matrix[j][n-i-1]); // 1和2交换
                swap(matrix[i][j], matrix[n-i-1][n-j-1]); // 1和3交换 
                swap(matrix[i][j], matrix[n-j-1][i]); // 1和4交换
            }
        }
    }
};

解法二：辅助空间

• 如何计算对应位置？
  1. 先关于y=-x对角线对称：\(x_1=y_0;\ y_1=x_0\)
  2. 然后关于纵轴对称：\(x_2=x_1=y_0;\ y_2=n-1-y_1=n-1-x_0\)
• 二维vector初始化方法
  • 初始化为另一个已知vector：vector<vector<int>> tmp = matrix;
  • 初始化为row * cul大小的0矩阵：vector<vector<int>> tmp(row, vector<int>(cul, 0));
• 一维vector初始化方法：vector<int> vec(len, 0);长度为len，初始化值为0

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int N = matrix.size();
        // vector<vector<int>> output(N, vector<int>(N, 0));//初始化N * N二维动态数组，初始化值为0
        vector<vector<int>> tmp = matrix;
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                matrix[j][N-1-i] = tmp[i][j]; // 关于y=-x对称后再关于横轴对称
            }
        }
        return;
    }
};