Rotate Matrix: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place.
分析
4 bytes可以用一个int来存储，那就变成了NxN的int二维数组的旋转。
先弄几个例子看看向右旋转90度是怎么回事，我们从外到里顺时针给元素编号：
周长 = 4n - 4，步进=周长-n-1
1x1，周长1，步进0：
2x2，周长4，步进3：
3x3，周长8，步进6：
1
2
3
|
0 1 2 6 7 0
7 8 3 -> 5 8 1
6 5 4 4 3 2
|
4x4，周长12，步进9：
1
2
3
4
|
0 1 2 3 9 10 11 0
11 12 13 4 -> 8 15 12 1
10 15 14 5 7 14 13 2
9 8 7 6 6 5 4 3
|
从最外圈到里圈变动，格子里的数字 = (原数字+步进) % 周长
结果，这个分析失败了，因为缺少坐标关系，后面很难弄，不过给后面带来了思路
继续分析
这次把坐标填上：
1
2
3
|
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,2) (2,2)
|
其实旋转可以看成是从四个顶点开始，都按照顺时针方向，挨个把自己的弄到90度的位置上去比如：
1
2
3
4
5
6
7
8
|
-->
o o
^ |
| v
o o
<--
|
如果我们知道了左上角的第一个顶点的位置，那么就能够知道其他3个顶点的位置：
1
2
3
4
|
(r, [c]++) （[r]++, c+n-1)
([r+n-1]--,c) (r+n-1, [c+n-1]--)
|
上面这个图中r=行，c=列，都是从0开始，边长为n，[]里的代表遍历时变动的维度，++/--代表变动的方式。
然后怎么把整个替换掉，我们可以从最外圈旋转，然后再旋转里圈的：
1
2
3
4
5
|
第一步 第二步
0 1 2 3 9 10 11 0 9 10 11 0
11 12 13 4 --> 8 12 13 1 --> 8 15 12 1
10 15 14 5 7 15 14 2 7 14 13 2
9 8 7 6 6 5 4 3 6 5 4 3
|
而且第layer层的周长=n - 2 * layer，layer从0开始。
解法1
一共有几圈=n/2，第一圈的左上角是(0,0)，第二圈的左上角是(1,1)，以此类推：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public void rotateMatrix(int[][] matrix, int n) {
for (int i = 0; i < n / 2; i++) {
int length = n - 2 * i;
int firstRow = i;
int firstCol = i;
int lastRow = firstRow + length - 1;
int lastCol = firstCol + length - 1;
for (int j = 0; j < length - 1; j++) {
int leftTop = matrix[firstRow][firstCol + j];
// leftBottom -> leftTop
matrix[firstRow][firstCol + j] = matrix[lastRow - j][firstCol];
// rightBottom -> leftBottom;
matrix[lastRow - j][firstCol] = matrix[lastRow][lastCol - j];
// rightTop -> rightBottom
matrix[lastRow][lastCol - j] = matrix[firstRow + j][lastCol];
// leftTop -> rightTop
matrix[firstRow + j][lastCol] = leftTop;
}
}
}
|
注意上面的 j < length -1 ，因为一条边的最后一个元素就是另一条边的第一个元素，所以我们不能遍历到它。
解法2优化
可以发现firstRow==firstCol和lastRow==lastCol，因此可以省去一些变量：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
for (int i = 0; i < n / 2; i++) {
int length = n - 2 * i;
int first = i;
int last = first + length - 1;
for (int j = 0; j < length - 1; j++) {
int leftTop = matrix[first][first + j];
// leftBottom -> leftTop
matrix[first][first + j] = matrix[last - j][first];
// rightBottom -> leftBottom;
matrix[last - j][first] = matrix[last][last - j];
// rightTop -> rightBottom
matrix[last][last - j] = matrix[first + j][last];
// leftTop -> rightTop
matrix[first + j][last] = leftTop;
}
}
|
评论