给你一幅由 N × 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]
]
方法一:使用辅助数组
我们以题目中的示例二
[
5
1
9
11
2
4
8
10
13
3
6
7
15
14
12
16
]
\begin{bmatrix} 5 & 1 & 9 & 11 \\ 2 & 4 & 8 & 10 \\ 13 & 3 & 6 & 7 \\ 15 & 14 & 12 & 16 \end{bmatrix}
?????521315?14314?98612?1110716??????
作为例子,分析将图像旋转 90 度之后,这些数字出现在什么位置。
对于矩阵中的第一行而言,在旋转后,它出现在倒数第一列的位置:
[ 5 1 9 11 ° ° ° ° ° ° ° ° ° ° ° ° ] ? 旋 转 后 [ ° ° ° 5 ° ° ° 1 ° ° ° 9 ° ° ° 11 ] \begin{bmatrix} 5 & 1 & 9 & 11 \\ \circ & \circ & \circ & \circ \\ \circ & \circ & \circ & \circ \\ \circ & \circ & \circ & \circ \\ \end{bmatrix} \Rightarrow{旋转后} \begin{bmatrix} \circ & \circ & \circ & 5 \\ \circ & \circ & \circ & 1 \\ \circ & \circ & \circ & 9 \\ \circ & \circ & \circ & 11 \end{bmatrix} ?????5°°°?1°°°?9°°°?11°°°???????旋转后?????°°°°?°°°°?°°°°?51911??????
并且,第一行的第 x x x 个元素在旋转后恰好是倒数第一列的第 x x x 个元素。
对于矩阵中的第二行而言,在旋转后,它出现在倒数第二列的位置:
[
°
°
°
°
2
4
8
10
°
°
°
°
°
°
°
°
]
?
旋
转
后
[
°
°
2
°
°
°
4
°
°
°
8
°
°
°
10
°
]
\begin{bmatrix} \circ & \circ & \circ & \circ \\ 2 & 4 & 8 & 10 \\ \circ & \circ & \circ & \circ \\ \circ & \circ & \circ & \circ \end{bmatrix} \Rightarrow {旋转后} \begin{bmatrix} \circ & \circ & 2 & \circ \\ \circ & \circ & 4 & \circ \\ \circ & \circ & 8 & \circ \\ \circ & \circ & 10 & \circ \end{bmatrix}