Leetcode 48- 向右旋转图片90°
1. 题目描述
很简单的需求，将一个二维数组向右旋转90°，栗子：1
2
3
4
5
6
7
8
9
10
11
12
13给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
:anger:要求: 必须就地变换，只能开O(1)级别的空间。
2. 思路
反正在草稿纸上大致画了一下，规律就是原来的a[i][j],旋转后被放到了a[j][n-1-i]的位置上，于是。。我傻乎乎的开始了3段式交换1
2
3int tmp=a[i][j];
a[i][j]=a[j][n-1-i];
a[j][n-1-i]=tmp;
写到一半。。。尼玛的。。发现根本不是这么回事。因为这两个位置不是对称的，我们下次还会可能访问matrix原来的a[j][n-1-i]元素，可是现在被我们替换掉了。
然后我也不知道咋办，于是就先胡乱试试，先转置一下(a[i][j]=a[j][i])，于是我惊奇的发现就是转置后再水平对称一次。所以就是2次二重循环，时间复杂度O(N^2),空间复杂度O(1)。
3. 代码
Java 实现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
35
36
37
38
39
40
41
42
43
44
45
46
47/**
* @ClassName RoateImage
* @Deacription // TODO
* @Author LiuZhian
* @Date 2019-10-30 17:00
* @Version 1.0
**/
public class RightRoateImage48 {
// 之前的a[i][j],旋转后成了a[j][n-1-i]
public void rotate(int[][] matrix) {
int n = matrix.length;
// 1. 先将矩阵转置
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
// 2. 再左右对称
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = tmp;
}
}
}
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
RightRoateImage48 r = new RightRoateImage48();
r.rotate(matrix);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.println(matrix[i][j]);
}
}
}
}
