【LeetCode48：旋转图像（附Java代码）】

一、题目描述

1.题目内容

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

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
原题链接：https://leetcode.cn/problems/rotate-image/

2.样例

二、解决方案

1.算法流程

1）分析

题目中要求“原地”进行矩阵旋转操作，“原地”的理解为：在原输入矩阵matrix所对应的内存位置中进行操作。所以可以从两个角度解决本题：

• （1）直接在matrix上进行操作，通过矩阵旋转前后对应元素之间的坐标关系实现；
• （2）借助辅助矩阵tempMatrix拷贝matrix的内容，内存中tempMatrix和matrix对应不同的区域，然后通过旋转前后的元素坐标之间的关系实现（题目中说不让使用辅助矩阵，但借助辅助矩阵的方法一次就过了，而且官方题解方法一就是借助辅助矩阵…）；

不管使用那种方法实现，重点均是找到矩阵旋转前后的元素坐标之间的关系。

以样例中的4×4矩阵为例，我们看一下其旋转前后对应元素坐标之间的关系：

可以看到，对于原输入矩阵matrix和旋转90度后的矩阵rotatedMatrix，rotatedMatrix中的第col列数据为matrix中的第n-1-col行数据，且rotatedMatrix中的第col列数据从row=0,1,…,n与matrix中的第n-1-col行数据从col=0,1,…,n元素一一对应。
由此得到rotatedMatrix与matrix对应元素之间的坐标关系为：

以元素rotatedMatrix[0][3]=5为例，其对应matrix[4-1-3][0]=matrix[0][0]。

2）算法流程

• 创建一个辅助矩阵tempMatrix，对matrix进行拷贝，因此其大小为n×n，且矩阵内容与matrix完全一致；
• 此时，可将matrix、tempMatrix分别视为公式中的rotatedMatrix和matrix；
• 以tempMatrix为对照矩阵，在matrix上利用二者对应元素之间的关系完成旋转操作，以遵守“原地”操作的条件；

此处借助辅助矩阵实现，其实官方题解中的方法三，通过两次翻转矩阵替换旋转的方式也很好理解，感兴趣的可去官网查看。

2.Java代码

1）核心代码

    public static void rotate(int[][] matrix){
        // 构建辅助矩阵，且拷贝matrix的内容
        int[][] tempMatrix=new int[matrix.length][];
        for(int i=0;i<matrix.length;i++){
            tempMatrix[i]=new int[matrix[i].length];
            for(int j=0;j<matrix[i].length;j++){
                tempMatrix[i][j]=matrix[i][j];
            }
        }
        // 借助tempMatrix在matrix上完成旋转操作的实现
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                matrix[i][j]=tempMatrix[matrix.length-1-j][i];
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

很显然，借助辅助矩阵的代价就是拿空间换时间了…

2）完整测试代码

/**
 * LeetCode48：旋转图像
 * */
import java.util.Arrays;

public class RotateMatrix {
    public static void main(String[] args) {
        int[][] matrix=new int[3][];
        matrix[0]=new int[]{1,2,3};
        matrix[1]=new int[]{4,5,6};
        matrix[2]=new int[]{7,8,9};

//        printMatrix(matrix);
        rotate(matrix);
    }

    /**
     * 矩阵旋转90度
     * 1.创建辅助矩阵tempMatrix=matrix（这里是指矩阵数据对应元素相同，但二者内存中不在同一位置）；
     * 2.基于tempMatrix进行旋转：matrix的第i列数据对应tempMatrix的第n-1-i行；
     * */
    public static void rotate(int[][] matrix){
        // 构建辅助矩阵，且拷贝matrix的内容
        int[][] tempMatrix=new int[matrix.length][];
        for(int i=0;i<matrix.length;i++){
            tempMatrix[i]=new int[matrix[i].length];
            for(int j=0;j<matrix[i].length;j++){
                tempMatrix[i][j]=matrix[i][j];
            }
        }
        // 借助tempMatrix在matrix上完成旋转操作的实现
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                matrix[i][j]=tempMatrix[matrix.length-1-j][i];
            }
        }
    }
    // 遍历矩阵
    public static void printMatrix(int[][] matrix){
        int rows= matrix.length;
        for(int i=0;i<rows;i++){
            System.out.println(Arrays.toString(matrix[i]));
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47