LeetCode 48. 旋转图像

Categories:

Tags:

题目描述
思路分析
1. 解法一：转置 + 水平翻转（推荐）
2. 解法二：四格循环原地旋转
相似题目

题目描述

✅ 48. 旋转图像

思路分析

解法一：转置 + 水平翻转（推荐）

核心思路：

顺时针旋转 90° 后，位置 (i, j) 的元素会移动到 (j, n-1-i)。

不借助辅助矩阵，将操作拆分为两步：

主对角线转置：交换 matrix[i][j] 与 matrix[j][i]，位置 (i, j) 变为 (j, i)。

每行水平翻转：交换 matrix[i][j] 与 matrix[i][n-1-j]，位置 (j, i) 变为 (j, n-1-i)。

合并效果：(i, j) → 转置 → (j, i) → 水平翻转 → (j, n-1-i) ✓

转置时只需遍历上三角（j 从 i+1 开始），避免重复交换回原位。

复杂度分析：

时间复杂度：O(n²)，其中 n 为矩阵边长，需遍历矩阵所有元素

空间复杂度：O(1)，原地操作，无需额外矩阵

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++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        // 第二步：每行左右翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0, k = n - 1; j < k; j++, k--) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][k];
                matrix[i][k] = tmp;
            }
        }
    }
}

func rotate(matrix [][]int) {
	n := len(matrix)
	// 第一步：沿主对角线转置，只遍历上三角避免重复交换
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
	// 第二步：每行左右翻转
	for i := 0; i < n; i++ {
		for j, k := 0, n-1; j < k; j, k = j+1, k-1 {
			matrix[i][j], matrix[i][k] = matrix[i][k], matrix[i][j]
		}
	}
}

解法二：四格循环原地旋转

核心思路：

顺时针旋转 90° 时，矩阵中每 4 个位置构成一个旋转环： (i, j) → (j, n-1-i) → (n-1-i, n-1-j) → (n-1-j, i) → (i, j)

只需遍历矩阵左上角四分之一区域（行 i ∈ [0, n/2)，列 j ∈ [i, n-1-i)），对每个位置依次进行 4 个格子的轮换。

仅用一个临时变量完成 4 格的循环赋值，真正做到 O(1) 空间。

复杂度分析：

时间复杂度：O(n²)，其中 n 为矩阵边长，每个元素恰好被访问一次

空间复杂度：O(1)，仅使用一个临时变量

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 只遍历左上角四分之一区域，每次同时旋转 4 个对称位置
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int tmp = 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] = tmp;
            }
        }
    }
}

func rotate(matrix [][]int) {
	n := len(matrix)
	// 只遍历左上角四分之一区域，每次同时旋转 4 个对称位置
	for i := 0; i < n/2; i++ {
		for j := i; j < n-1-i; j++ {
			tmp := 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] = tmp
		}
	}
}

相似题目

题目	难度	考察点
54. 螺旋矩阵	中等	矩阵模拟
59. 螺旋矩阵 II	中等	矩阵模拟
73. 矩阵置零	中等	矩阵原地操作
289. 生命游戏	中等	矩阵原地操作
885. 螺旋矩阵 III	中等	矩阵模拟
1886. 判断矩阵经轮转后是否一致	简单	矩阵旋转

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/62515833