Description

  • 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

Example 1

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]
]

Interface

1
2
3
4
5
6
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {

    }
};

Solution

问题主要在于不能使用额外的2维矩阵去求解，思路其实就是由内圈到外圈将整个矩阵顺时针旋转 90°，一是存放当前位置的值以便旋转后将值赋值到旋转后的新位置，二是推导出从当前位置到旋转后的新位置的公式，上述一二操作循环四个数字即可。整个算法的时间复杂度是 $O(n^2)​$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int temp = 0, row = 0, col = 0, tmp = 0;
        for (int i = 0; i < matrix.size() / 2; ++i) {
            for (int j = i; j < matrix.size() - i - 1; ++j) {
                row = i; col = j;
                for (int k = 0; k < 5; ++k) {
                    tmp = matrix[row][col];
                    matrix[row][col] = temp;
                    temp = row;
                    row = col;
                    col = matrix.size() - 1 - temp;
                    temp = tmp;
                }
            }
        }
    }
};

/*
  n represents the matrix's dimension
  row represents the row of the present position
  col represents the column of the present position

  Actually, the transform function can be written as:
  new_row = col
  new_col = n - row - 1

  Example:
  1 2 3        7 2 1        7 4 1
  4 5 6   ->   4 5 6   ->   8 5 2
  7 8 9	       9 8 3        9 6 3
*/

Improvement

LeetCode 讨论区上见到的，先将矩阵按主对角线翻转，再将翻转后的矩阵的每一行进行逆序，就可以完成对矩阵的 90° 旋转。

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

/*
  Example:
  1 2 3        1 4 7        7 4 1
  4 5 6   ->   2 5 8   ->   8 5 2
  7 8 9	       3 6 9        9 6 3
*/