【世界速看料】LeetCode HOT 100：旋转图像

2022-12-15 16:19:14 来源：博客园

(资料图)

题目：48. 旋转图像

题目描述：

给你一个正方形矩阵数组，将其中的所有元素都顺时针旋转90度，得到旋转之后的矩阵数组。本题要求必须在原地修改，不能使用额外空间。

思路：

看到这个题，如果可以使用额外空间，很简单，把行都放到列上就行。假设原数组num[row][col]，放到新列上就是num[col][n − row − 1]。但是本题要求必须原地修改，那么上述对应关系就不能直接用了，因为会导致元素被覆盖，等遍历到num[col][n − row − 1]元素的时候，原来该下标的值就找不到了。这类旋转矩阵的题，都可以采用一种宏观思想，也就是分圈。举个例子:

1	2	3
4	5	6
7	8	9

转化之后为：

7	4	1
8	5	2
9	6	3

可以一圈一圈的进行旋转，定义好圈的左上角和右下角，然后一圈圈的往里推进，就能把矩阵中所有圈都旋转完，矩阵也就旋转完了。然后在每一圈里，每个元素找到旋转之后的位置规律即可。找规律也是有方法的，将这一圈的数字可以划分为组，例如上面的矩阵，最外圈所有元素，假设划分为两组。第一组(1, 3, 9, 7)，第二组(2, 6, 8, 4)。旋转之后，第一组：1 -> 3, 3 -> 9, 9 -> 7, 7 -> 1，第二组也一样，2 -> 6, 6 -> 8, 8 -> 4, 4 -> 2。那么咱们假设，圈左上角坐标为(a, b)，右下角坐标为(c, d)。那么第一组的四个数字，坐标分别为(a, b), (a, d), (c, d), (c, b)，那么旋转关系就是(a, b) -> (a, d)、(a, d) -> (c, d)、(c, d) -> (c, b)、(c, b) -> (a, b)。第二组坐标分别为(a, b + 1), (a + 1, d), (c, d - 1), (c - 1, b)，旋转关系为(a, b + 1) -> (a + 1, d)、(a + 1, d) -> (c, d - 1)、(c, d - 1) -> (c - 1, b)、(c - 1, b) -> (a, b + 1)。如果将上面的1都转化为一个变量i，那么规律就出来了。每一个组的转化关系都是(a, b + i) -> (a + i, d)、(a + i, d) -> (c, d - i)、(c, d - i) -> (c - i, b)、(c - i, b) -> (a, b + i)。这个i肯定从0开始，但是什么时候终止呢，也就是一圈的数要分成几组呢？很简单，d - b组，因为在一圈中有d- b组元素，需要找到对应位置进行旋转。例如上面的矩阵，最外圈需要以7开头和以4开头的两组需要进行旋转。

步骤：

1、找到矩阵最外圈的左上角坐标和右下角坐标，作为参数开始调用旋转一圈的函数2、在旋转一圈的函数中，拿到两个坐标，开始根据位置规律，进行对应的旋转3、每次一圈完毕之后，左上角坐标加1，右下角坐标减1，当左上角坐标大于右下角坐标的时候，终止。说明所有圈都旋转完毕

代码：

public void rotate(int[][] matrix) {        // 使用左上角(a, b)，右下角(c, d)来规划一个圈        int a = 0, b = 0;        int c = matrix.length - 1, d = matrix[0].length - 1;        while (a < c) {            // 将(a, b)和(c, d)划出来的圈，进行旋转            // 然后将圈往里推进一圈            rotateEdge(matrix, a++, b++, c--, d--);        }    }    // 将以(a, b)和(c, d)划出来的圈，进行旋转    public void rotateEdge(int[][] matrix, int a, int b, int c, int d) {        int temp;        // 将圈中每一个元素都找到对应的位置，进行旋转。        for (int i = 0; i < d - b; i++) {            temp = matrix[a][b + i];            matrix[a][b + i] = matrix[c - i][b];            matrix[c - i][b] = matrix[c][d - i];            matrix[c][d - i] = matrix[a + i][d];            matrix[a + i][d] = temp;        }    }

因为矩阵一定是正方形矩阵，所以代码可以进行适当优化，左上角和右下角坐标，x轴和y轴坐标一定一样。所以可以从四个变量，缩减为两个。代码如下：

public void rotate(int[][] matrix) {        // 使用左上角(a, b)，右下角(c, d)来规划一个圈        int a = 0, c = matrix.length - 1;        while (a < c) {            // 将(a, b)和(c, d)划出来的圈，进行旋转            // 然后将圈往里推进一圈            rotateEdge(matrix, a++, c--);        }    }    // 将以(a, b)和(c, d)划出来的圈，进行旋转    public void rotateEdge(int[][] matrix, int a, int c) {        int temp;        // 将圈中每一个元素都找到对应的位置，进行旋转。        for (int i = 0; i < c - a; i++) {            temp = matrix[a][a + i];            matrix[a][a + i] = matrix[c - i][a];            matrix[c - i][a] = matrix[c][c - i];            matrix[c][c - i] = matrix[a + i][c];            matrix[a + i][c] = temp;        }    }

关键词：可以进行什么时候顺时针旋转