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] ]
本题要求将一个矩阵顺时针旋转90度，且不使用多余的数组保存中间结果。看似很简单，其实有很多点需要注意。 如上图所示，旋转的时候，其实每次都只有四个元素互相交换，如上图的黑色方框和红色方框。每次旋转时，先保存最上面那个元素，比如黑框，先把2保存下来，然后把9填到2的位置，把15填到9的位置…最后把2填到8的位置，这样整个旋转过程只使用了1个临时变量，达到了in-place的目的。 每次换框的时候，比如由黑框换到红框，x–,y++。在旋转的时候，需要充分利用方框四周的4个三角形是全等三角形，求出4个顶点的坐标。自己摸索一下就能找到里面的关系。 完整代码如下：
class Solution {
public:
void rotate(vector<vector<int> >& matrix)
{
int offset = matrix.size() – 1, max_y = matrix.size() – 1;
for (int i = 0; i < matrix.size() / 2; i++) {
int x = offset, y = 0;
for (int j = i; j < max_y; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i + x][j – y];
matrix[i + x][j – y] = matrix[i + x + y][j – y + x];
matrix[i + x + y][j – y + x] = matrix[i + y][j + x];
matrix[i + y][j + x] = tmp;
x–;
y++;
}
offset -= 2;
max_y–;
}
}
};本代码提交AC，用时4MS。
二刷。更简单，更安全的做法是先对行逆序，就是第一行和最后一行互换，第二行和倒数第二行互换…然后对对称元素互换。详细过程参考讨论区：https://discuss.leetcode.com/topic/6796/a-common-method-to-rotate-the-image。完整代码如下：
class Solution {
public:
void rotate(vector<vector<int> >& matrix)
{
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[0].size(); ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};本代码提交AC，用时6MS。