48.旋转图像

LeetCode LeetCode 热题100 数组数学矩阵

发布时间 : 2000-01-10 00:04

字数:1.8k 阅读 :

评论:

48.旋转图像

48.旋转图像

48.1 题目

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

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

示例 1：

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

示例 2：

输入：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

48.2 题解

方法一：先转置后翻转

思路

先沿主对角线转置矩阵（交换 matrix[i][j] 和 matrix[j][i]），然后翻转每一行（交换 matrix[i][j] 和 matrix[i][n-1-j]）。这两步操作组合起来就是顺时针旋转 90 度。

核心思想：旋转 90° = 转置 + 水平翻转。

具体步骤：

转置矩阵：交换 matrix[i][j] 和 matrix[j][i]（j > i）。
翻转每一行：交换 matrix[i][j] 和 matrix[i][n-1-j]（j < n/2）。

举例：对于 matrix = [[1,2,3],[4,5,6],[7,8,9]]：

转置后：[[1,4,7],[2,5,8],[3,6,9]]
翻转每行后：[[7,4,1],[8,5,2],[9,6,3]]

复杂度分析

时间复杂度：O(n²)，遍历矩阵两次。
空间复杂度：O(1)，原地修改。

代码

// 方法一：先转置后翻转
static void Rotate1(int[][] matrix)
{
    int matrixLength = matrix.Length; // 获取矩阵的行列数

    // 先转置矩阵
    for (int i = 0; i < matrixLength; i++)
    {
        for (int j = i + 1; j < matrixLength; j++)
        {
            // 交换 matrix[i][j] 和 matrix[j][i]
            (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
        }
    }

    // 再翻转每一行
    for (int i = 0; i < matrixLength; i++)
    {
        for (int j = 0; j < matrixLength / 2; j++)
        {
            // 交换 matrix[i][j] 和 matrix[i][matrixLength - j - 1]
            (matrix[i][j], matrix[i][matrixLength - j - 1]) = (matrix[i][matrixLength - j - 1], matrix[i][j]);
        }
    }
}

方法二：四个一组旋转

思路

将矩阵分成若干个 2×2 的小块（对于奇数 n，中心元素不动），每次旋转四个位置的元素：左上→右上→右下→左下→左上。通过临时变量保存一个位置的值，然后依次移动。

核心思想：四角循环交换，一次处理四个元素。

具体步骤：

遍历矩阵外层到内层（i 从 0 到 n/2）。
对于每层，遍历 j 从 i 到 n-1-i-1：
- 保存 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] = 临时变量

举例：对于 matrix = [[1,2,3],[4,5,6],[7,8,9]]：

外层 i=0，j=0：旋转 (0,0)→(0,2)→(2,2)→(2,0)→(0,0)
j=1：旋转 (0,1)→(1,2)→(2,1)→(1,0)→(0,1)
结果：[[7,4,1],[8,5,2],[9,6,3]]

复杂度分析

时间复杂度：O(n²)，遍历矩阵四分之一。
空间复杂度：O(1)，原地修改，只用一个临时变量。

代码

// 方法二：四个一组旋转
static void Rotate2(int[][] matrix)
{
    int matrixLength = matrix.Length; // 获取矩阵的行列数

    // 四个一组旋转
    for (int i = 0; i < (matrixLength + 1) / 2; i++)
    {
        for (int j = 0; j < matrixLength / 2; j++)
        {
            // 临时保存左下角的值
            int temp = matrix[matrixLength - 1 - j][i];

            // 右下角移动到左下角
            matrix[matrixLength - 1 - j][i] = matrix[matrixLength - 1 - i][matrixLength - 1 - j];

            // 右上角移动到右下角
            matrix[matrixLength - 1 - i][matrixLength - 1 - j] = matrix[j][matrixLength - 1 - i];

            // 左上角移动到右上角
            matrix[j][matrixLength - 1 - i] = matrix[i][j];

            // 左下角移动到左上角
            matrix[i][j] = temp;
        }
    }
}

48.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

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

        // 示例 1：
        // 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
        // 输出：[[7,4,1],[8,5,2],[9,6,3]]

        // 示例 2：
        // 输入：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

        #endregion

        #region 测试

        // 示例 1
        int[][] matrix1 = new int[][]
        {
            new int[] { 1, 2, 3 },
            new int[] { 4, 5, 6 },
            new int[] { 7, 8, 9 }
        };
        Rotate1(matrix1); // 旋转矩阵的方法1
        Console.WriteLine("示例1 方法1 输出：");
        PrintMatrix(matrix1); // 打印旋转后的矩阵

        int[][] matrix1_2 = new int[][]
        {
            new int[] { 1, 2, 3 },
            new int[] { 4, 5, 6 },
            new int[] { 7, 8, 9 }
        };
        Rotate2(matrix1_2); // 旋转矩阵的方法2
        Console.WriteLine("示例1 方法2 输出：");
        PrintMatrix(matrix1_2); // 打印旋转后的矩阵

        // 示例 2
        int[][] matrix2 = new int[][]
        {
            new int[] { 5, 1, 9, 11 },
            new int[] { 2, 4, 8, 10 },
            new int[] { 13, 3, 6, 7 },
            new int[] { 15, 14, 12, 16 }
        };
        Rotate1(matrix2); // 旋转矩阵的方法1
        Console.WriteLine("示例2 方法1 输出：");
        PrintMatrix(matrix2); // 打印旋转后的矩阵

        int[][] matrix2_2 = new int[][]
        {
            new int[] { 5, 1, 9, 11 },
            new int[] { 2, 4, 8, 10 },
            new int[] { 13, 3, 6, 7 },
            new int[] { 15, 14, 12, 16 }
        };
        Rotate2(matrix2_2); // 旋转矩阵的方法2
        Console.WriteLine("示例2 方法2 输出：");
        PrintMatrix(matrix2_2); // 打印旋转后的矩阵

        #endregion
    }

    #region 答案

    // 方法一：先转置后翻转
    static void Rotate1(int[][] matrix)
    {
        int matrixLength = matrix.Length; // 获取矩阵的行列数

        // 先转置矩阵
        for (int i = 0; i < matrixLength; i++)
        {
            for (int j = i + 1; j < matrixLength; j++)
            {
                // 交换 matrix[i][j] 和 matrix[j][i]
                (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
            }
        }

        // 再翻转每一行
        for (int i = 0; i < matrixLength; i++)
        {
            for (int j = 0; j < matrixLength / 2; j++)
            {
                // 交换 matrix[i][j] 和 matrix[i][matrixLength - j - 1]
                (matrix[i][j], matrix[i][matrixLength - j - 1]) = (matrix[i][matrixLength - j - 1], matrix[i][j]);
            }
        }
    }

    // 方法二：四个一组旋转
    static void Rotate2(int[][] matrix)
    {
        int matrixLength = matrix.Length; // 获取矩阵的行列数

        // 四个一组旋转
        for (int i = 0; i < (matrixLength + 1) / 2; i++)
        {
            for (int j = 0; j < matrixLength / 2; j++)
            {
                // 临时保存左下角的值
                int temp = matrix[matrixLength - 1 - j][i];

                // 右下角移动到左下角
                matrix[matrixLength - 1 - j][i] = matrix[matrixLength - 1 - i][matrixLength - 1 - j];

                // 右上角移动到右下角
                matrix[matrixLength - 1 - i][matrixLength - 1 - j] = matrix[j][matrixLength - 1 - i];

                // 左上角移动到右上角
                matrix[j][matrixLength - 1 - i] = matrix[i][j];

                // 左下角移动到左上角
                matrix[i][j] = temp;
            }
        }
    }


    // 打印矩阵
    static void PrintMatrix(int[][] matrix)
    {
        int n = matrix.Length; // 获取矩阵的行列数
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                Console.Write(matrix[i][j] + " "); // 打印矩阵的元素
            }
            Console.WriteLine(); // 换行
        }
    }

    #endregion
}

48.4 运行结果

示例1 方法1 输出：
7 4 1 
8 5 2 
9 6 3 
示例1 方法2 输出：
7 4 1 
8 5 2 
9 6 3 
示例2 方法1 输出：
15 13 2 5 
14 3 4 1 
12 6 8 9 
16 7 10 11 
示例2 方法2 输出：
15 13 2 5
14 3 4 1
12 6 8 9
16 7 10 11

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com