题目链接：Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:

Could you do this in-place?

这道题的要求是将n*n的矩阵顺时针旋转90°，要求原地旋转，即不申请额外空间。

1. 逐个旋转

要旋转[i, j]位置的元素，即按顺序移动数组元素[i, j] -> [j, n-i-1] -> [n-i-1, n-j-1] -> [n-j-1, i] -> [i, j]。

时间复杂度：O(n2)

空间复杂度：O(1)

 1 class Solution
 2 {
 3 public:
 4     void rotate(vector
   
     > &matrix) 5 { 6 int n = matrix.size(); 7 for(int i = 0; i < n / 2; ++ i) 8 for(int j = i; j < n - i - 1; ++ j) 9 { 10 int temp = matrix[i][j]; 11 matrix[i][j] = matrix[n - j - 1][i]; 12 matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; 13 matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; 14 matrix[j][n - i - 1] = temp; 15 } 16 } 17 };
   

或者

 1 class Solution
 2 {
 3 public:
 4     void rotate(vector
   
     > &matrix) 5 { 6 int n = matrix.size(); 7 for(int i = 0; i < n / 2; ++ i) 8 for(int j = i; j < n - i - 1; ++ j) 9 { 10 swap(matrix[i][j], matrix[n - j - 1][i]); 11 swap(matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1]); 12 swap(matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1]); 13 } 14 } 15 };
   

2. 先翻转，在对换

思路如下：

1 2 3     7 8 9     7 4 1
4 5 6  => 4 5 6  => 8 5 2
7 8 9     1 2 3     9 6 3

先将数组从上到下翻转，然后按左对角线交换对称元素。

时间复杂度：O(n2)

空间复杂度：O(1)

 1 class Solution
 2 {
 3 public:
 4     void rotate(vector
   
     > &matrix) 5 { 6 reverse(matrix.begin(), matrix.end()); 7 for(int i = 0; i < matrix.size(); ++ i) 8 for(int j = 0; j < i; ++ j ) 9 swap(matrix[i][j], matrix[j][i]); 10 } 11 };
   

?