旋转图像[中等]

爱被打了一巴掌 2024-02-19 08:06 31阅读 0赞

优质博文：[IT-BLOG-CN][]

### 一、题目 ###

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

**示例 1：**

![d2e706f77efc434da0c955d673594328.png][]

**输入：** `matrix = [[1,2,3],[4,5,6],[7,8,9]]`  
**输出：** `[[7,4,1],[8,5,2],[9,6,3]]`

**示例 2：**

![79cec77904834acdb6a8e1e812f93480.png][]

**输入：** `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]]`

> `n == matrix.length == matrix[i].length`  
> `1 <= n <= 20`  
> `-1000 <= matrix[i][j] <= 1000`

### 二、代码 ###

【1】我们先不进行原地旋转，而是使用**辅助数组**进行，我们通过案例寻找规律：

[5  1  9  11]
    [2  4  8  10]       
    [13 3  6  7 ]         
    [15 14 12 16]

我们将图像旋转90度之后，我们看下第一行，旋转后他出现在倒数第一列的位置：可以发现第一行的`x`元素落到了倒数第一列的第`x`个元素。

[5  1  9  11]                 [o  o  o  5] 
    [o  o  o  o ]  ----> 旋转后   [o  o  o  1] 
    [o  o  o  o ]                 [o  o  o  9] 
    [o  o  o  o ]                 [o  o  o 11]

对于矩阵中的第二行，我们旋转后看下：对于矩阵中的第三行和第四行同理。这样我们可以得到规律：\*\*对于矩阵中第`i`行的第`j`个元素，在旋转后，它出现在倒数第`i`列的第`j`个位置。\*\*我们将其翻译成代码。由于矩阵中的行列从`0`开始计数，因此对于矩阵中的元素`matrix[row][col]`，在旋转后，它的新位置为`matrixnew[col][n−1−row]`。

[o  o  o  o ]                 [o  o  2  o] 
    [2  4  5  10]  ----> 旋转后   [o  o  3  o] 
    [o  o  o  o ]                 [o  o  4  o] 
    [o  o  o  o ]                 [o  o  10 o]

我们使用一个与`matrix`大小相同的辅助数组`matrixnew`，临时存储旋转后的结果。我们遍历`matrix`中的每一个元素，根据上述规则将该元素存放到`matrixnew` 中对应的位置。在遍历完成之后，再将`matrixnew`中的结果复制到原数组中即可。

class Solution {
        
        public void rotate(int[][] matrix) {
        
            // 先创建相同的二位数据进行优化
            int n = matrix.length;
            int[][] matrixNew = new int[n][n];
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    matrixNew[j][n-1-i] = matrix[i][j];
                }
            }
            for (int i = 0; i < n; ++i) {
        
                for (int j = 0; j < n; ++j) {
        
                    matrix[i][j] = matrixNew[i][j];
                }
            }
        }
    }

**时间复杂度：** `O(N2)`其中`N`是`matrix`的边长。  
**空间复杂度：** `O(N2)`我们需要使用一个和`matrix`大小相同的辅助数组。

【2】去除额外空间，使用**原地旋转**：我们尝试在不使用额外内存空间的情况下进行矩阵的旋转，那么如何在方法一的基础上完成原地旋转呢？

我们观察方法一中的关键等式：`matrixnew[col][n−row−1]=matrix[row][col]` 它阻止了我们进行原地旋转，这是因为如果我们直接将`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`获取它原来的值：

temp                 = matrix[col][n−row−1]
    matrix[col][n−row−1] = matrix[row][col]

那么`matrix[col][n−row−1]`经过旋转操作之后会到哪个位置呢？我们还是使用方法一中的关键等式，不过这次，我们需要将

row = col
    col = n−row−1

带入关键等式，就可以得到：

matrix[n−row−1][n−col−1] = matrix[col][n−row−1]

同样地，直接赋值会覆盖掉`matrix[n−row−1][n−col−1]`原来的值，因此我们还是需要使用一个临时变量进行存储，不过这次，我们可以直接使用之前的临时变量`temp`：

temp                     = matrix[n−row−1][n−col−1]
    matrix[n−row−1][n−col−1] = matrix[col][n−row−1]
    matrix[col][n−row−1]     = matrix[row][col]

我们再重复一次之前的操作`matrix[n−row−1][n−col−1]`经过旋转操作之后会到哪个位置呢？

row = n−row−1
    col = n−col−1

带入关键等式，就可以得到：`matrix[n−col−1][row]=matrix[n−row−1][n−col−1]`写进去：

temp                      = matrix[n−col−1][row]
    matrix[n−col−1][row]      = matrix[n−row−1][n−col−1]
    matrix[n−row−1][n−col−1]  = matrix[col][n−row−1]
    matrix[col][n−row−1]      = matrix[row][col]

再来一次`matrix[n−col−1][row]`经过旋转操作之后回到哪个位置呢？

row = n−col−1
    col = row

带入关键等式，就可以得到：`matrix[row][col]=matrix[n−col−1][row]`我们回到了最初的起点`matrix[row][col]`，也就是说：

matrix[row][col]
    matrix[col][n−row−1]
    matrix[n−row−1][n−col−1]
    matrix[n−col−1][row]

这四项处于一个循环中，并且每一项旋转后的位置就是下一项所在的位置！因此我们可以使用一个临时变量`temp`完成这四项的原地交换：

temp                     = matrix[row][col]
    matrix[row][col]         = matrix[n−col−1][row]
    matrix[n−col−1][row]     = matrix[n−row−1][n−col−1]
    matrix[n−row−1][n−col−1] = matrix[col][n−row−1]
    matrix[col][n−row−1]     = temp

当我们知道了如何原地旋转矩阵之后，还有一个重要的问题在于：我们应该枚举哪些位置`(row,col)`进行上述的原地交换操作呢？由于每一次原地交换四个位置，因此：  
【1】当`n`为偶数时，我们需要枚举`n^2/4=(n/2)×(n/2)`个位置，可以将该图形分为四块，以`4×4`的矩阵为例：保证了不重复、不遗漏；

![975d44d16c15459392d886a0a85bbf1b.png][]

【2】当`n`为奇数时，由于中心的位置经过旋转后位置不变，我们需要枚举`(n^2−1)/4=((n−1)/2)×((n+1)/2)`个位置，需要换一种划分的方式，以`5×5`的矩阵为例：同样保证了不重复、不遗漏，矩阵正中央的点无需旋转。

![040f90bbd07b4545bf54158d772588f7.png][]

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(N^2)`其中`N`是`matrix`的边长。我们需要枚举的子矩阵大小为`O(⌊n/2⌋×⌊(n+1)/2⌋)=O(N^2)`。  
**空间复杂度：** `O(1)`为原地旋转。

**【3】用翻转代替旋转：** 我们还可以另辟蹊径，用翻转操作代替旋转操作。我们还是以题目中的示例二

[5  1  9  11]
    [2  4  8  10]       
    [13 3  6  7 ]         
    [15 14 12 16]

作为例子，先将其通过水平轴翻转得到：

[5  1  9  11]                [15 14 12 16]
    [2  4  8  10]    -->反转后    [13 3  6  7] 
    [13 3  6  7 ]                [2  4  8  10] 
    [15 14 12 16]                [5  1  9  11]

再根据主对角线翻转得到：

[5  1  9  11]                [15 13 2  5]
    [2  4  8  10]    -->反转后    [14 3  4  1] 
    [13 3  6  7 ]                [12 6  8  9] 
    [15 14 12 16]                [16 7 10  11]

就得到了答案。这是为什么呢？对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换，即`matrix[row][col]`水平轴翻转`matrix[n−row−1][col]`对于主对角线翻转而言，我们只需要枚举对角线左侧的元素，和右侧的元素进行交换，即`matrix[row][col]`主对角线翻转`matrix[col][row]`将它们联立即可得到：

matrix[row][col]  水平轴翻转     matrix[n−row−1][col]
                      主对角线翻转   matrix[col][n−row−1]

和方法一、方法二中的关键等式：`matrixnew[col][n−row−1]=matrix[row][col]`是一致的。

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

**时间复杂度：**`O(N^2)`，其中`N`是`matrix`的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。  
**空间复杂度：** `O(1)`。为原地翻转得到的原地旋转。

[IT-BLOG-CN]: https://it-blog-cn.com/blogs/algorithm/topic/medium/rotate_image.html
[d2e706f77efc434da0c955d673594328.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/879dc101da8c45cbad68c35b6c956e39.png
[79cec77904834acdb6a8e1e812f93480.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/8841801497f447d8a72c188a9bb42889.png
[975d44d16c15459392d886a0a85bbf1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/d70e3c7fd8604820b52441ff68320a4e.png
[040f90bbd07b4545bf54158d772588f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/5d534cb79a654e97bc2ea07a2f0eb262.png