LeetCode 48. 旋转图像

约 5 分钟
文章信息 21 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 华为 拼多多 小米 商汤 虾皮 LeetCode 热题 100 面试经典 150 题
标签
数组 数学 矩阵 矩阵问题
目录

题目描述

✅ 48. 旋转图像

image-20230305131821519

image-20230305131827245

题意分析

给定一个 n x n 的二维矩阵表示图像，将它顺时针旋转 90 度。函数没有返回值，结果直接体现在传入的矩阵上。

两个关键约束：一是方向必须是顺时针，旋转后原来最下面一行会立起来变成最左边一列的位置关系要想清楚，方向搞反是常见事故；二是必须原地修改，题面明确禁止「另开一个矩阵旋转后写回」，这正是本题的考点——去掉原地限制它就是一道抄写题。

约束信号：矩阵保证是方阵（行列数相等），$n$ 最大只有 20，规模不构成压力，难点全在下标推导；$n = 1$ 时矩阵旋转后原样不动，是天然的边界用例。

解法：转置矩阵后反转每一行

核心思路

顺时针旋转 90 度的坐标映射是 (i, j) → (j, n - 1 - i)。直接把值写到目标位置会覆盖尚未搬走的数据，另开矩阵又违反原地要求，因此把这个映射拆成两个可原地完成的操作。

先沿主对角线转置：(i, j) → (j, i)；再反转转置后的每一行：(j, i) → (j, n - 1 - i)。两步复合恰好得到目标坐标，所以无需凭图形记方向，面试时写出坐标映射即可验证。

转置阶段只遍历主对角线上方的元素，使每对镜像位置恰好交换一次；行反转用首尾双指针，也让每对元素只交换一次。这两个不变量保证操作不会互相抵消，并满足 $O(1)$ 额外空间。

解题步骤

  • 遍历上三角区域：对每个 i，令 j 从 i + 1 开始，交换 matrix[i][j] 与 matrix[j][i]。
  • 逐行使用双指针交换首尾元素，直到两指针相遇。
  • 原矩阵 [[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]]。
  • 若面试追问逆时针旋转，可在转置后反转每一列；仍应通过坐标映射确认方向。

代码实现

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 value = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = value;
            }
        }

        for (int[] row : matrix) {
            reverse(row);
        }
    }

    private void reverse(int[] row) {
        int left = 0;
        int right = row.length - 1;

        while (left < right) {
            int value = row[left];
            row[left] = row[right];
            row[right] = value;
            left++;
            right--;
        }
    }
}

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 := range matrix {
        reverseInts(matrix[i])
    }
}

func reverseInts(nums []int) {
    left, right := 0, len(nums)-1

    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

复杂度分析

  • 时间复杂度：$O(n^2)$。转置与逐行反转处理的元素总数都与 $n^2$ 同阶。
  • 空间复杂度：$O(1)$。只使用临时变量和下标，直接修改原矩阵。

关键点总结

  • 先写目标坐标 (i, j) → (j, n - 1 - i)，再验证变换顺序，比死记“翻转哪一边”可靠。
  • 转置只能扫描对角线一侧；若扫描整个矩阵，每对元素会交换两次。
  • 顺时针是“主对角线转置 + 反转每一行”；反转列得到的是逆时针。
  • 四点轮换同样是 $O(n^2)$ 时间、$O(1)$ 空间，但下标和遍历边界更容易出错，不是白板首选。

易错点总结

  • 转置时 j 从 0 开始：上下三角会把同一对元素交换两次，矩阵恢复原样。
  • 转置后反转每一列：方向会变成逆时针。
  • 直接执行 matrix[j][n-1-i] = matrix[i][j]：目标格的旧值尚未搬走就被覆盖。
  • 新建矩阵后只写 matrix = rotated：Java 和 Go 都只是重新绑定局部引用，调用方看不到结果，也不满足原地要求。
  • 将该写法用于非方阵：主对角线转置依赖行列数相等；本题保证输入为方阵。

相似题目

题目 难度 考察点
54. 螺旋矩阵 中等 按层收缩边界，模拟螺旋遍历顺序
59. 螺旋矩阵 II 中等 反向操作：按螺旋顺序往方阵里填数
73. 矩阵置零 中等 借首行首列做标记，实现 $O(1)$ 空间原地改
867. 转置矩阵 简单 单独练转置这一步，且矩阵不保证是方阵
面试题 01.07. 旋转矩阵 中等 与本题同题，可换四点轮换法再练一遍