一.題目描述
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)。
