旋转矩阵
1.题目内容
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
1
2
| 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
|
示例 2：
1
2
| 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
|
2.解法
（1）辅助矩阵
思路及算法
如下图所示，矩阵顺时针旋转 90º 后，可找到以下规律：
1
2
| matrix[i] [j]→matrix[j] [n−1−i]
原索引位置→旋转后索引位置
|
根据以上「元素旋转公式」，考虑遍历矩阵，将各元素依次写入到旋转后的索引位置。但仍存在问题：在写入一个元素 matrix[i] [j]→matrix[j] [n−1−i]后，原矩阵元素 matrix[j] [n−1−i] 就会被覆盖（即丢失），而此丢失的元素就无法被写入到旋转后的索引位置了。
为解决此问题，考虑借助一个「辅助矩阵」暂存原矩阵，通过遍历辅助矩阵所有元素，将各元素填入「原矩阵」旋转后的新索引位置即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| //Java
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 深拷贝 matrix -> tmp
int[][] tmp = new int[n][];
for (int i = 0; i < n; i++)
tmp[i] = matrix[i].clone();
// 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[j][n - 1 - i] = tmp[i][j];
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| //C++
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// 深拷贝 matrix -> tmp
vector<vector<int>> tmp = matrix;
// 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[j][n - 1 - i] = tmp[i][j];
}
}
}
};
|
复杂度分析
（2）原地修改
思路及算法
考虑不借助辅助矩阵，通过在原矩阵中直接「原地修改」，实现空间复杂度 O(1) 的解法。
以位于矩阵四个角点的元素为例，设矩阵左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩阵旋转 90º 后，相当于依次先后执行 D→A , C→D , B→C , A→B 修改元素，即如下「首尾相接」的元素旋转操作：A←D←C←B←A
如上图所示，由于第 1 步 D→A 已经将 A 覆盖（导致 A 丢失），此丢失导致最后第 4 步 A→B 无法赋值。为解决此问题，考虑借助一个「辅助变量 tmp 」预先存储 A ，此时的旋转操作变为：
暂存tmp=A
A←D←C←B←tmp
如上图所示，一轮可以完成矩阵 4 个元素的旋转。因而，只要分别以矩阵左上角 1/41/41/4 的各元素为起始点执行以上旋转操作，即可完整实现矩阵旋转。
具体来看，当矩阵大小 n 为偶数时，取前 n/2 行、前 n/2 列的元素为起始点；当矩阵大小 n 为奇数时，取前 n/2\ 行、前 (n+1)/2 列的元素为起始点。
令 matrix[i] [j]=A，根据文章开头的元素旋转公式，可推导得适用于任意起始点的元素旋转操作：
暂存tmp=matrix[i] [j]
matrix[i][j]←matrix[n−1−j] [i]←matrix[n−1−i] [n−1−j]←matrix[j] [n−1−i]←tmp
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| //Java
class Solution {
public void rotate(int[][] matrix) {
// 设矩阵行列数为 n
int n = matrix.length;
// 起始点范围为 0 <= i < n / 2 , 0 <= j < (n + 1) / 2
// 其中 '/' 为整数除法
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
// 暂存 A 至 tmp
int tmp = matrix[i][j];
// 元素旋转操作 A <- D <- C <- B <- tmp
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| //C++
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
// 设矩阵行列数为 n
int n = matrix.size();
// 起始点范围为 0 <= i < n / 2 , 0 <= j < (n + 1) / 2
// 其中 '/' 为整数除法
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
// 暂存 A 至 tmp
int tmp = matrix[i][j];
// 元素旋转操作 A <- D <- C <- B <- tmp
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
};
|
复杂度分析
- 时间复杂度 O(N^2^) ： 其中 N 为输入矩阵的行（列）数。需要将矩阵中每个元素旋转到新的位置，即对矩阵所有元素操作一次，使用 O(N^2^) 时间。
- 空间复杂度 O(1) ： 临时变量 tmp 使用常数大小的额外空间。值得注意，当循环中进入下轮迭代，上轮迭代初始化的 tmp 占用的内存就会被自动释放，因此无累计使用空间。