## 一.題目描述 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 <iostream> #include <vector> using namespace std; class Solution { public: void turnRightImage(vector<vector<int> >& 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)`。