文章目录
题目
标题和出处
标题：旋转图像
出处：48. 旋转图像
难度
5 级
题目描述
要求
给定一个 n × n \texttt{n} \times \texttt{n} n×n 的二维矩阵 matrix \texttt{matrix} matrix 表示一个图像。请你将图像顺时针旋转 90 \texttt{90} 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例
示例 1：
输入：
matrix
=
[[1,2,3],[4,5,6],[7,8,9]]
\texttt{matrix = [[1,2,3],[4,5,6],[7,8,9]]}
matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：
[[7,4,1],[8,5,2],[9,6,3]]
\texttt{[[7,4,1],[8,5,2],[9,6,3]]}
[[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]]
\texttt{matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]}
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]]
\texttt{[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]}
[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
示例 3：
输入：
matrix
=
[[1]]
\texttt{matrix = [[1]]}
matrix = [[1]]
输出：
[[1]]
\texttt{[[1]]}
[[1]]
示例 4：
输入：
matrix
=
[[1,2],[3,4]]
\texttt{matrix = [[1,2],[3,4]]}
matrix = [[1,2],[3,4]]
输出：
[[3,1],[4,2]]
\texttt{[[3,1],[4,2]]}
[[3,1],[4,2]]
数据范围
- matrix.length = n \texttt{matrix.length}=\texttt{n} matrix.length=n
- matrix[i].length = n \texttt{matrix[i].length}=\texttt{n} matrix[i].length=n
- 1 ≤ n ≤ 20 \texttt{1} \le \texttt{n} \le \texttt{20} 1≤n≤20
- -1000 ≤ matrix[i][j] ≤ 1000 \texttt{-1000} \le \texttt{matrix[i][j]} \le \texttt{1000} -1000≤matrix[i][j]≤1000
解法一
思路和算法
最直观的思路是新建一个与原矩阵相同大小的临时矩阵，将图像顺时针旋转 90 90 90 度之后的值存入临时矩阵，然后将临时矩阵复制回原矩阵即可。对于边长为 n n n 的矩阵，创建临时矩阵需要 O ( n 2 ) O(n^2) O(n2) 的额外空间，虽然没有达到 O ( 1 ) O(1) O(1) 的额外空间，但是这是思考的第一步，在此基础上进行优化，即可得到使用 O ( 1 ) O(1) O(1) 额外空间的解法。
对于 0 ≤ i , j < n 0 \le i,j < n 0≤i,j<n，旋转前位于第 i i i 行第 j j j 列的元素，旋转后将位于哪一行哪一列？该元素在旋转前所在位置为从上往下第 i i i 个和从左往右第 j j j 个（均为从 0 0 0 开始计数），旋转后所在位置为从右往左第 i i i 个和从上往下第 j j j 个（均为从 0 0 0 开始计数），因此旋转后将位于第 j j j 行第 n − 1 − i n-1-i n−1−i 列。
用 ( i , j ) (i,j) (i,j) 表示第 i i i 行第 j j j 列。根据上述分析可知，经过旋转之后，位于 ( i , j ) (i,j) (i,j) 的元素旋转到 ( j , n − 1 − i ) (j,n-1-i) (j,n−1−i)。同理可得，位于 ( j , n − 1 − i ) (j,n-1-i) (j,n−1−i) 的元素旋转到 ( n − 1 − i , n − 1 − j ) (n-1-i,n-1-j) (n−1−i,n−1−j)，位于 ( n − 1 − i , n − 1 − j ) (n-1-i,n-1-j) (n−1−i,n−1−j) 的元素旋转到 ( n − 1 − j , i ) (n-1-j,i) (n−1−j,i)，位于 ( n − 1 − j , i ) (n-1-j,i) (n−1−j,i) 的元素旋转到 ( i , j ) (i,j) (i,j)。因此，从 ( i , j ) (i,j) (i,j) 出发，共有 4 4 4 个位置的元素进行了旋转。
例如，考虑以下 5 × 5 5 \times 5 5×5 的矩阵，其中有 4 4 4 个非零元素。
0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 4 0 0 0 0 0 0 0 3 0 \begin{matrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \end{matrix} 0004010000000000000302000
在对该矩阵顺时针旋转 90 90 90 度之后，得到如下矩阵。
0 4 0 0 0 0 0 0 0 1 0 0 0 0 0 3 0 0 0 0 0 0 0 2 0 \begin{matrix} 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \end{matrix} 0003040000000000000201000
从一个位置出发，共有四个位置的元素进行了旋转，这四个位置的元素可以原地修改，不需要通过新建临时矩阵完成旋转。
由于从一个位置出发可以修改四个位置的元素，因此只需要将矩阵中的四分之一的位置作为旋转的起点，即可完成整个矩阵的旋转。
选择作为旋转的起点的四分之一的位置有多种选法，原则是选中的位置中，任意两个位置都不能通过旋转得到，例如 ( i , j ) (i,j) (i,j)、 ( j , n − 1 − i ) (j,n-1-i) (j,n−1−i)、 ( n − 1 − i , n − 1 − j ) (n-1-i,n-1-j) (n−1−i,n−1−j) 和 ( n − 1 − j , i ) (n-1-j,i) (n−1−j,i) 这四个位置中有且只有一个位置被选为旋转的起点。
一种选法是选择如下集合中的全部位置： { ( i , j ) ∣ 0 ≤ i < ⌊ n 2 ⌋ , i ≤ j < n − 1 − i } \{(i,j) | 0 \le i < \Big\lfloor \dfrac{n}{2} \Big\rfloor, i \le j < n - 1 - i\} {(i,j)∣0≤i<⌊2n⌋,i≤j<n−1−i}。注意到当 n n n 是奇数时，矩阵中心的元素不需要旋转。
以下两个矩阵分别显示 n = 4 n=4 n=4 和 n = 5 n=5 n=5 时的旋转起点和旋转规则。 A \text{A} A 表示旋转起点， A \text{A} A 的元素被旋转到 B \text{B} B， B \text{B} B 的元素被旋转到 C \text{C} C， C \text{C} C 的元素被旋转到 D \text{D} D， D \text{D} D 的元素被旋转到 A \text{A} A， X \text{X} X 表示当 n n n 是奇数时的矩阵中心的元素。
当 n = 4 n=4 n=4 时：
A A A B D A B B D D C B D C C C \begin{matrix} \text{A} & \text{A} & \text{A} & \text{B} \\ \text{D} & \text{A} & \text{B} & \text{B} \\ \text{D} & \text{D} & \text{C} & \text{B} \\ \text{D} & \text{C} & \text{C} & \text{C} \end{matrix} ADDDAADCABCCBBBC
当 n = 5 n=5 n=5 时：
A A A A B D A A B B D D X B B D D C C B D C C C C \begin{matrix} \text{A} & \text{A} & \text{A} & \text{A} & \text{B} \\ \text{D} & \text{A} & \text{A} & \text{B} & \text{B} \\ \text{D} & \text{D} & \text{X} & \text{B} & \text{B} \\ \text{D} & \text{D} & \text{C} & \text{C} & \text{B} \\ \text{D} & \text{C} & \text{C} & \text{C} & \text{C} \end{matrix} ADDDDAADDCAAXCCABBCCBBBBC
代码
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int rowEnd = n / 2;
for (int i = 0; i < rowEnd; i++) {
int columnEnd = n - 1 - i;
for (int j = i; j < columnEnd; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = temp;
}
}
}
}
复杂度分析
-
时间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n n n 是矩阵 matrix \textit{matrix} matrix 的边长。需要对矩阵中的每个元素进行旋转操作。
-
空间复杂度： O ( 1 ) O(1) O(1)。
解法二
思路和算法
可以换一个思路。首先将矩阵转置，然后将转置后的矩阵的每一行翻转，即可实现将矩阵顺时针旋转 90 90 90 度。
用 transposed \textit{transposed} transposed 表示将 matrix \textit{matrix} matrix 转置后的矩阵，用 reversed \textit{reversed} reversed 表示将 transposed \textit{transposed} transposed 的每一行翻转后的矩阵。
对于 0 ≤ i , j < n 0 \le i,j < n 0≤i,j<n，有 transposed [ i ] [ j ] = matrix [ j ] [ i ] , reversed [ i ] [ j ] = transposed [ i ] [ n − 1 − j ] \textit{transposed}[i][j]=\textit{matrix}[j][i], \textit{reversed}[i][j]=\textit{transposed}[i][n-1-j] transposed[i][j]=matrix[j][i],reversed[i][j]=transposed[i][n−1−j]。重新整理变量名，可以得到：
matrix [ i ] [ j ] = transposed [ j ] [ i ] = reversed [ j ] [ n − 1 − i ] \textit{matrix}[i][j]=\textit{transposed}[j][i]=\textit{reversed}[j][n-1-i] matrix[i][j]=transposed[j][i]=reversed[j][n−1−i]
因此 reversed \textit{reversed} reversed 即为将 matrix \textit{matrix} matrix 顺时针旋转 90 90 90 度之后的矩阵。
转置和水平翻转操作的顺序可以交换。首先将矩阵水平翻转，然后将水平翻转的矩阵转置，也可实现将矩阵顺时针旋转 90 90 90 度。
代码
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 temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0, k = n - 1; j < k; j++, k--) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][k];
matrix[i][k] = temp;
}
}
}
}
复杂度分析
-
时间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n n n 是矩阵 matrix \textit{matrix} matrix 的边长。需要对矩阵中的每个元素进行转置和水平翻转操作。
-
空间复杂度： O ( 1 ) O(1) O(1)。