【数据结构与算法】之旋转图像的求解算法
【摘要】
一、题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像，请将图像顺时针旋转 90 度。必须在原地旋转图像，这意味着需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例一：...
一、题目描述
- 给定一个 n × n 的二维矩阵 matrix 表示一个图像，请将图像顺时针旋转 90 度。
- 必须在原地旋转图像，这意味着需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
- 示例一：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
- 1
- 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]]
- 1
- 2
- 示例三：
输入：matrix = [[1]]
输出：[[1]]
- 1
- 2
- 示例四：
输入：matrix = [[1,2],[3,4]]
输出：[[3,1],[4,2]]
- 1
- 2
二、使用辅助数组求解
- 以题目中的示例二：
- 分析将图像旋转 90 度之后，这些数字出现在什么位置。对于矩阵中的第一行而言，在旋转后，它出现在倒数第一列的位置：
- 并且，第一行的第 x 个元素在旋转后恰好是倒数第一列的第 x 个元素。对于矩阵中的第二行而言，在旋转后，它出现在倒数第二列的位置：
- 对于矩阵中的第三行和第四行同理，这样可以得到规律：
对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。
- 1
- 由于矩阵中的行列从 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];
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- Java 算法示例如下：
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];
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 复杂度分析：
-
- 时间复杂度：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 的矩阵为例，同样保证了不重复、不遗漏，矩阵正中央的点无需旋转：
- C 算法示例如下：
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;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- Java 算法示例如下：
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;
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 复杂度分析
-
- 时间复杂度：O(N2)，其中 N 是 matrix 的边长，需要枚举的子矩阵大小为 O(⌊n/2⌋×⌊(n+1)/2⌋)=O(N2)。
-
- 空间复杂度：O(1)，为原地旋转。
四、用翻转代替旋转
- 以题目中的示例二，用翻转操作代替旋转操作：
- 先将其通过水平轴翻转得到：
- 再根据主对角线翻转得到：
- 这就得到了答案，这是为什么呢？对于水平轴翻转而言，只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换，即
- 对于主对角线翻转而言，只需要枚举对角线左侧的元素，和右侧的元素进行交换，即
- 将它们联立即可得到：
- 和前两个方法中的关键等式是一样的，如下：
- C 的算法示例如下：
void swap(int* a, int* b) {
int t = *a;
*a = *b, *b = t;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
// 水平翻转
for (int i = 0; i < matrixSize / 2; ++i) {
for (int j = 0; j < matrixSize; ++j) {
swap(&matrix[i][j], &matrix[matrixSize - i - 1][j]);
}
}
// 主对角线翻转
for (int i = 0; i < matrixSize; ++i) {
for (int j = 0; j < i; ++j) {
swap(&matrix[i][j], &matrix[j][i]);
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- Java 算法示例如下：
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; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 主对角线翻转
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;
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 复杂度分析
-
- 时间复杂度：O(N2)，其中 N 是 matrix 的边长。对于每一次翻转操作，都需要枚举矩阵中一半的元素。
-
- 空间复杂度：O(1)，为原地翻转得到的原地旋转。
文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/Forever_wj/article/details/119333060
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）