摘要：
题目
给你一幅由 $N \times N$ 矩阵表示的图像，其中每个像素的大小为 $4$ 字节。请你设计一种算法，将图像旋转 $90$ 度。
不占用额外内存空间能否做到？
示例1：
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例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]
]
原地旋转方法
先将数组按对角线翻折：
此时得到的数组每行和目标数组相反，只需要再将每行数组按中轴线翻折。
注意两次翻折的起始和终止，切记不能重复翻折（会折回去）。
比如第一次翻折不能写成 for (int j = 0; j < len; j++)。如果这样，在 i 向下遍历过程中，会将之前折的折回去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution0x0 {
public void rotate(int[][] matrix) {
int len = matrix.length;
for (int i = 0 ; i < len; i++) {
for (int j = i + 1; j < len; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
int mid = len / 2;
for (int i = 0; i < len; i++) {
for (int j = 0; j < mid; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][len - 1 - j];
matrix[i][len - 1 - j] = temp;
}
}
}
}
|
借用临时 $N \times N$ 数组（需额外空间）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution0x1 {
public void rotate(int[][] matrix) {
int len = matrix.length;
int[][] temp = new int[len][len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
temp[j][len - 1 - i] = matrix[i][j];
}
}
for (int i = 0; i < len; i++) {
System.arraycopy(temp[i], 0, matrix[i], 0, len);
}
}
}
|