一、题目描述
- 给定一个 n × n 的二维矩阵 matrix 表示一个图像，请将图像顺时针旋转 90 度。
- 必须在原地旋转图像，这意味着需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
- 示例一：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
输入：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]]
输入：matrix = [[1]]
输出：[[1]]
输入：matrix = [[1,2],[3,4]]
输出：[[3,1],[4,2]]
二、使用辅助数组求解
- 以题目中的示例二：
 - 分析将图像旋转 90 度之后，这些数字出现在什么位置。对于矩阵中的第一行而言，在旋转后，它出现在倒数第一列的位置：
- 并且，第一行的第 x 个元素在旋转后恰好是倒数第一列的第 x 个元素。对于矩阵中的第二行而言，在旋转后，它出现在倒数第二列的位置：
- 对于矩阵中的第三行和第四行同理，这样可以得到规律：
对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。
- 由于矩阵中的行列从 0 开始计数，因此对于矩阵中的元素 matrix[row][col]，在旋转后，它的新位置为 matrixnew [col][n?row?1]。
- 这样以来，使用一个与 matrix 大小相同的辅助数组 matrixnew，临时存储旋转后的结果。遍历 matrix 中的每一个元素，根据上述规则将该元素存放到 matrixnew 中对应的位置。在遍历完成之后，再将 matrixnew 中的结果复制到原数组中即可。
- C 算法示例如下：
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
int matrix_new[matrixSize][matrixSize];
for (int i = 0; i < matrixSize; i++) {
for (int j = 0; j < matrixSize; j++) {
matrix_new[i][j] = matrix[i][j];
}
}
for (int i = 0; i < matrixSize; ++i) {
for (int j = 0; j < matrixSize; ++j) {
matrix[j][matrixSize - i - 1] = matrix_new[i][j];
}
}
}
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] matrix_new = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix_new[j][n - i - 1] = matrix[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix[i][j] = matrix_new[i][j];
}
}
}
}
- 复杂度分析：
-
- 时间复杂度：O(N2)，其中 N 是 matrix 的边长。
-
- 空间复杂度：O(N2)。需要使用一个和 matrix 大小相同的辅助数组。
三、原地旋转
- 题目中要求尝试在不使用额外内存空间的情况下进行矩阵的旋转，也就是说，需要「原地旋转」这个矩阵。那么我们在上面方法的基础上完成原地旋转呢？
- 观察上面方法的关键等式：
- 它阻止了进行原地旋转，这是因为如果直接将 matrix[row][col] 放到原矩阵中的目标位置 matrix[col][n?row?1]：
- 原矩阵中的 matrix[col][n?row?1] 就被覆盖，这并不是想要的结果。因此可以考虑用一个临时变量 temp 暂存 matrix[col][n?row?1] 的值，这样虽然 matrix[col][n?row?1] 被覆盖，还是可以通过 temp 获取它原来的值：
- 那么 matrix[col][n?row?1] 经过旋转操作之后会到哪个位置呢？还是使用上面方法中的关键等式，不过这次需要将：
- 同样地，直接赋值会覆盖掉 matrix[n?row?1][n?col?1] 原来的值，因此还是需要使用一个临时变量进行存储，不过这次，可以直接使用之前的临时变量 temp：
- 再重复一次之前的操作，matrix[n?row?1][n?col?1] 经过旋转操作之后会到哪个位置呢？
- 再来一次，matrix[n?col?1][row] 经过旋转操作之后回到哪个位置呢？
- 回到了最初的起点 matrix[row][col]，也就是说：
- 这四项处于一个循环中，并且每一项旋转后的位置就是下一项所在的位置。因此可以使用一个临时变量 temp 完成这四项的原地交换：
- 当知道如何原地旋转矩阵之后，还有一个重要的问题在于：应该枚举哪些位置 (row,col) 进行上述的原地交换操作呢？由于每一次原地交换四个位置，因此：
-
- 当 n 为偶数时，需要枚举 n2/4=(n/2)×(n/2) 个位置，可以将该图形分为四块，以 4×4 的矩阵为例，保证了不重复、不遗漏；
-
- 当 n 为奇数时，由于中心的位置经过旋转后位置不变，需要枚举 (n2?1)/4=((n?1)/2)×((n+1)/2) 个位置，需要换一种划分的方式，以 5×5 的矩阵为例，同样保证了不重复、不遗漏，矩阵正中央的点无需旋转：
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
for (int i = 0; i < matrixSize / 2; ++i) {
for (int j = 0; j < (matrixSize + 1) / 2; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[matrixSize - j - 1][i];
matrix[matrixSize - j - 1][i] = matrix[matrixSize - i - 1][matrixSize - j - 1];
matrix[matrixSize - i - 1][matrixSize - j - 1] = matrix[j][matrixSize - i - 1];
matrix[j][matrixSize - i - 1] = temp;
}
}
}
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < (n + 1) / 2; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
}
- 复杂度分析
-
- 时间复杂度：O(N2)，其中 N 是 matrix 的边长，需要枚举的子矩阵大小为 O(?n/2?×?(n+1)/2?)=O(N2)。
-
|
