矩阵转置
顺时针旋转 $90^\circ$ 可以拆成两步来做。
第一步先沿主对角线转置，也就是交换 $matrix[i][j]$ 和 $matrix[j][i]$。这样原来的行就变成了列。第二步再将每一行左右翻转，就完成了顺时针旋转。
例如转置后，矩阵元素的位置关系已经接近目标结果，再通过每行反转把列顺序调整过来，最终就得到顺时针旋转后的矩阵。整个过程都在原数组上进行，满足题目要求的原地操作。
时间复杂度 $O(n^2)$
空间复杂度 $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; ++j) {
int tmp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = tmp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; ++j) {
int tmp = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = matrix[i][j];
matrix[i][j] = tmp;
}
}
}
}
|