48.Rotate Image

Tags: array Medium

Links: https://leetcode.com/problems/rotate-image/

---

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 NOT**allocate 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]
]

---

Answer:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n == 0) return;
        int boundary = n / 2;

        for (int i = 0; i < boundary; ++i){
            for (int j = i; j < n - i - 1; ++j){
                int tmp = std::move(matrix[i][j]);
                matrix[i][j] = std::move(matrix[n-1-j][i]);
                matrix[n-1-j][i] = std::move(matrix[n-1-i][n-1-j]);
                matrix[n-1-i][n-1-j] = std::move(matrix[j][n-1-i]);
                matrix[j][n-1-i] = std::move(tmp);
            }
        }
    }
};

# test result
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Rotate Image.
Memory Usage: 9 MB, less than 97.56% of C++ online submissions for Rotate Image.

解析：

对于这种旋转问题，直觉上第一反应是可以通过旋转矩阵求解，也就是得到一个通项公式。

首先建立一个映射，无论题目里给出的矩阵是多少维，描述其中每一个元素的维数总是二维的，即行号和列号，将其画在平面直角坐标系里，单位长度为1，则旋转相当于顺时针旋转90°或逆时针旋转270°。

其次我们需要找到旋转所围绕的中心点，但它是一直变化的且不在原点。更一般的，我们来研究下平面直角坐标系里的平移、旋转的新坐标和原坐标之间的关系。

规定逆时针旋转角度$\theta$ 为正，向右上平移方向为正。

1. 绕原点的旋转

这种情形最简单，在矩阵论课程或者线性代数的课程里已经学过通过旋转矩阵来得到新坐标。

$$ x=rcos\phi \ y=rsin\phi \ x^{'}=rcos(\theta+\phi) \ y^{'}=rsin(\theta+\phi) \ \therefore x^{'} = xcos\theta - y sin\theta \ y^{'} = xsin\theta+ycos\theta $$ 从而得到： $$ \left[\begin{array}{l}{x^{\prime}} \ {y^{\prime}}\end{array}\right]=\left[\begin{array}{ll}{\cos \theta} & {-\sin \theta} \ {\sin \theta} & {\cos \theta}\end{array}\right] *\left[\begin{array}{l}{x} \ {y}\end{array}\right] $$

1. 平移变换

$$ x^{'} = x + t_x \ y^{'} = y + t_y \ $$

$$\left[\begin{array}{c}{x^{\prime}} \\ {y^{\prime}} \\ {1}\end{array}\right]=\left[\begin{array}{ccc}{1} & {0} & {t_x} \\ {0} & {1} & {t_y} \\ {0} & {0} & {1}\end{array}\right] *\left[\begin{array}{l}{x} \\ {y} \\ {1}\end{array}\right]$$

1. 绕任意点的旋转

• 先平移到原点
• 绕原点旋转
• 在平移恢复到平移前的位置

上述过程发现，如果最初平移了t，最后一步就需要平移-t，所以上述过程描述成矩阵为： $$ \left[\begin{array}{c}{x^{\prime}} \ {y^{\prime}} \ {1}\end{array}\right] = \left[\begin{array}{ccc}{1} & {0} & {-t_x} \ {0} & {1} & {-t_y} \ {0} & {0} & {1}\end{array}\right] *\left[\begin{array}{ccc}{\cos \theta} & {-\sin \theta} & {0} \ {\sin \theta} & {\cos \theta} & {0} \ {0} & {0} & {1}\end{array}\right] *\left[\begin{array}{ccc}{1} & {0} & {t_x} \ {0} & {1} & {t_y} \ {0} & {0} & {1}\end{array}\right] *\left[\begin{array}{l}{x} \ {y} \ {1}\end{array}\right] $$ 所以得到新坐标只需要将上述计算出结果即可，对于本题，角度是固定的为-90°或270°，则$cos\theta=0, sin\theta = -1​$

，所以得到： $$ x^{\prime} = y + t_y - t_x \ y^{\prime} = -x - t_x - t_y \ \because t_x = t_y = t\ \therefore x^{\prime} = y \ y^{\prime} = -x -2t $$ 所以问题求解的关键在于求t的值。注意到题目里是个正方形矩阵，则如果真正求解t，则：

double t = (-1.0) * (matrix.size()- 1) / 2;

实际上只需要知道2t值即可，通过上述可知为-(n-1)。所以得到： $$ x^{\prime} = y \ y^{\prime} = n - 1 - x $$ 接下来的问题就是考虑遍历矩阵元素来执行变换，不妨对于坐标为$(i, j)$的元素进行变换： $$ (i,j) \rightarrow (j,n-1-i) \rightarrow (n-1-i,n-1-j) \rightarrow (n-1-j,i) \rightarrow (i,j) $$ 通过上述推导可以发现，四次变换后回到起始点，图形示意如下。

观察发现，对于每一行的元素，并不是所有元素都需要被遍历，只需要遍历从起始点到倒数第二个点，如果把矩阵按奇数阶和偶数阶来划分，则遍历的过程如下：

其中只有红色标记的点需要遍历，其他的点都可以通过红色点来求出相应的坐标。对于究竟有多少个点需要遍历，我们需要考虑一下矩阵的阶数：奇数阶矩阵和偶数阶矩阵，偶数阶矩阵又要考虑4k+2阶和4k阶的区别。

奇数阶矩阵的特点是总有一个点不需要变换，偶数阶矩阵里无论是4k还是4k+2阶，都能像右边的图一样，所有点都需要变动。

设最外层为第0层，矩阵边长为n。可以发现，无论是奇数阶还是偶数阶矩阵，需要遍历的层数都是从$[0, n/2)$。对于每一层里需要遍历的元素，无论是奇数阶还是偶数阶矩阵，都是从$[i, n - 1 - i)$。变成工作只需要把上述过程翻译成代码即可。