LeetCode 旋转图像【数学】【数组】

ゝ一世哀愁。 2022-09-09 09:22 157阅读 0赞

# 旋转图像 #

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

# 解题 #

## 1 数学 ##

/** * 矩阵翻转= 矩阵转置+翻转每行 * * 时间复杂度：O(n^2) * * 空间复杂度 O(1) */
        public void rotate(int[][] matrix) { 
            //矩阵转置
            for (int i = 0; i < matrix.length; i++) { 
                for (int j = 0; j < i; j++) { 
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
    
            //行翻转
            for (int i = 0; i < matrix.length; i++) { 
                for (int j = 0; j < matrix.length / 2; j++) { 
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[i][matrix.length - j - 1];
                    matrix[i][matrix.length - j - 1] = temp;
                }
            }
        }

## 2 数组 ##

**ps:** 找规律，得出 newRow=oldCol，newCol=n-1-oldRow  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 2]

/** * 时间复杂度 O(n^2) * 空间复杂度 O(1) */
        public void rotate1(int[][] matrix) { 
    
            int n = matrix.length;
    
            for (int i = 0; i < (n + 1) / 2; i++) { 
                for (int j = 0; j < n / 2; j++) { 
    
                    int[] tmp = new int[4];
                    int row = i;
                    int col = j;
                    //记录旋转的数
                    for (int k = 0; k < 4; k++) { 
                        tmp[k] = matrix[row][col];
                        int temp = row;
                        row = col;
                        col = n - 1 - temp;
                    }
    
                    //旋转
                    for (int k = 0; k < 4; k++) { 
                        matrix[row][col] = tmp[(k + 3) % 4];
                        int temp = row;
                        row = col;
                        col = n - 1 - temp;
                    }
                }
            }
        }

## 3 直接旋转 ##

/** * 时间复杂度 O(n^2) * 空间复杂度 O(1) */
        public void rotate1(int[][] matrix) { 
            int n = matrix.length;
            for (int i = 0; i < (n + 1) / 2; i++) { 
                for (int j = 0; j < n / 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;
                }
            }
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 3]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8820de0138f44011abf5785ef74f86c0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/0d1ca7a8e7424f3ca9f640799913d6d7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/eef3edcd271a4a0eaccf2ff32968aef2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/cf3846babb2a4c47887aa84753fa02e7.png