【Leetcode Top 100】48. 旋转图像

问题背景

给定一个 $n\times n$ 的二维矩阵 $matrix$ 表示一个图像。请你将图像顺时针旋转 $90$ 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

数据约束

• $n==matrix.length==matrix[i].length$
• $1\le n\le 20$
• $-1000\le matrix[i][j]\le 1000$

解题过程

比较好想的做法是定义一个辅助矩阵，将对应行排列到相应的列中，再把所有元素覆盖回来。这样的做法需要 $O(N)$ 的额外空间，就不写了。

另一个解决旋转问题的思路是将旋转拆解为多个翻转，本题中可以将顺时针旋转 $90$ 度拆解为矩阵上下翻转和沿着主对角线翻转两个操作。这样的想法问题在于，面对第一次见到的问题，不一定能快速地找到拆解的方案，需要平时多积累。

还可以直接移动元素，需要注意的是当矩阵的阶数为奇数时，需要考察的范围是一个矩形。考虑到这种情况，需要将行或者列的循环结束条件修正为 $i(j)<(n+1)/2$。

具体实现

翻转矩阵

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 - 1 - i][j];
                matrix[n - 1 - i][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;
            }
        }
    }
}

移动元素

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 - 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;
            }
        }
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/143986899

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！