Rotate Image
最后更新于：2022-04-01 22:55:35
## 一.题目描述
You are given an `n×n` 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?
## 二.题目分析
由于要求将图像顺时针旋转90度，最简单的做法就是画个图出来观察旋转90度之后的图像的情况，经过分析可知，顺时针旋转90度就是将原来的图像的最后一行作为第一列，倒数第二行作为第二列，因此类推，第一行作为最后一列。如果不考虑in-place条件，我们可以创建一个大小为`n×n`的一个二维数组来进行复制操作，然后将旋转后的图像拷贝回原来的图像中。这种做法的时间复杂度为`O(n^2)`，空间复杂度为`O(n^2)`。
但是，题目希望能in-place进行，由于无论图像进行什么角度的选择，左上角的点都可以看作坐标系的原点，因此，将一幅图像抽象成`3×3`的情形，可以从中找出一些规律：
1 2 3
4 5 6
7 8 9
顺时针旋转90度之后的图像的抽象即为：
7 4 1
8 5 2
9 6 3
可以归纳出一种等价的变换：
首先，将矩阵的每个元素沿着沿着主对角线进行交换；
1 2 3 — 1 4 7
4 5 6 -> 2 5 8
7 8 9 — 3 6 9
然后，每列的元素沿着水平中线对称翻转一次，在这里，第一列和第三列关于第二列对称，因此只需将一、三列元素对调，即可得到旋转90度后的结果。
1 4 7 — 7 4 1
2 5 8 -> 8 5 2
3 6 9 — 9 6 3
## 三.示例代码
~~~
#include
#include
using namespace std;
class Solution
{
public:
void turnRightImage(vector >& image)
{
int imaSize = image.size();
// 主对角线以下的元素与主对角线上元素沿着主对角线垂直方向对换
for (int i = 1; i < imaSize; i++)
{
for (int j = i - 1; j >= 0; j--)
swap(image[i][j], image[j][i]);
}
for (int k = 0; k < imaSize / 2; k++)
{
for (int l = 0; l < imaSize; l++)
swap(image[l][k], image[l][imaSize - k - 1]);
}
}
};
~~~
一个测试结果：
## 四.小结
这道题要求in-place运算，其实对于此类要求，应该更多考虑转换前后数据/矩阵的关系。根据以上的分析我们知道，将一张图片进行顺时针90度旋转，可等价于将矩阵的每个元素沿着沿着主对角线进行交换，然后沿着水平中线翻转一次，或者先将矩阵元素沿着水平中线翻转一次，然后再沿对角线交换，这样可以做到in-place运行，空间复杂度为`O(1)`。
';