48. 旋转图像

力扣题目链接 (opens new window)

题目描述

给定一个 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

思路

顺时针旋转90度，听起来有点抽象，很多录友第一反应是找规律，看旋转后每个位置的元素来自哪里。

但这样找出来的规律，写成代码比较复杂。

有个更巧妙的方法：先转置，再左右翻转（或者先上下翻转，再转置，但那样是逆时针90度）。

什么是转置？就是沿着主对角线翻折，matrix[i][j]和matrix[j][i]交换。

什么是左右翻转？就是每一行内部，左右对称地交换元素。

为什么这样就是顺时针旋转90度呢？

我们来看一个例子：

原矩阵：
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

刚好就是顺时针旋转90度的结果！

所以思路很清晰：

1. 转置矩阵（沿主对角线交换）
2. 左右翻转每一行

模拟过程

以 matrix = [[1,2,3],[4,5,6],[7,8,9]] 为例：

第1步：转置矩阵

沿主对角线交换元素：matrix[i][j] 与 matrix[j][i] 交换。循环时 j 从 i+1 开始，避免重复交换。

第2步：左右翻转

每一行内部左右翻转：matrix[i][j] 与 matrix[i][n-1-j] 交换。完成顺时针旋转 90°！

解题代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        // 第一步：转置矩阵（沿主对角线交换）
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {  // 注意j从i+1开始，避免重复交换
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        
        // 第二步：左右翻转每一行
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                swap(matrix[i][j], matrix[i][n - 1 - j]);
            }
        }
    }
};

复杂度分析

• 时间复杂度：O(n²)，需要遍历矩阵的所有元素
• 空间复杂度：O(1)，原地操作

其他语言

Python3

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        
        # 第一步：转置矩阵（沿主对角线交换）
        for i in range(n):
            for j in range(i + 1, n):  # 注意j从i+1开始，避免重复交换
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # 第二步：左右翻转每一行
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]

Java

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // 第一步：转置矩阵（沿主对角线交换）
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {  // 注意j从i+1开始，避免重复交换
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // 第二步：左右翻转每一行
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

Go

func rotate(matrix [][]int) {
    n := len(matrix)
    
    // 第一步：转置矩阵（沿主对角线交换）
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {  // 注意j从i+1开始，避免重复交换
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    
    // 第二步：左右翻转每一行
    for i := 0; i < n; i++ {
        for j := 0; j < n / 2; j++ {
            matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
        }
    }
}

JavaScript

var rotate = function(matrix) {
    const n = matrix.length;
    
    // 第一步：转置矩阵（沿主对角线交换）
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {  // 注意j从i+1开始，避免重复交换
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    
    // 第二步：左右翻转每一行
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < Math.floor(n / 2); j++) {
            [matrix[i][j], matrix[i][n - 1 - j]] = [matrix[i][n - 1 - j], matrix[i][j]];
        }
    }
};

与代码随想录联系

这道题的巧妙之处在于，把一个看起来复杂的旋转操作，拆解成两个简单的操作：转置和翻转。

这种化繁为简的思想，在算法题中非常重要。遇到复杂操作时，不要急着找规律写代码，而是先想想能不能拆解成几个简单操作的组合。

类似的思想在代码随想录的很多题目中都有体现，比如链表反转、字符串处理等。

另外，录友们要注意转置时的循环边界：j从i+1开始，避免重复交换。这种细节很容易出错，建议画图模拟一遍加深理解。