跳到主要内容

48. 旋转图像

1. 题目简介​

难度：中等，原题链接：48. 旋转图像。

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

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

2. 问题分析​

顺时针旋转 90 度后，原来位于 (i, j) 的元素会移动到 (j, n - 1 - i)。连续旋转四次会回到原位，因此可以把这些位置作为一组，完成一次循环交换。

从 (i, j) 出发，按顺时针顺序得到四个位置：

  • (i, j)
  • (j, n - i - 1)
  • (n - i - 1, n - j - 1)
  • (n - j - 1, i)

把它们依次记为 A、B、C、D，需要让 A 的值移到 B，B 的值移到 C，C 的值移到 D，D 的值移到 A。代码始终以 A 为交换位置，依次与 B、C、D 交换，就能完成这个轮换。

每组只处理一次。代码取靠上的 (n + 1) / 2 行和靠左的 n / 2 列作为起点，除法按整数计算。边长为奇数时，这个范围包含中间行左侧的元素，但不会包含中心点；中心点旋转后仍在原位，无需处理。

3. 代码实现​

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int m = (n + 1) / 2;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m - n % 2; j++) {
                swap(matrix, i, j, j, n - 1 - i);
                swap(matrix, i, j, n - 1 - i, n - 1 - j);
                swap(matrix, i, j, n - 1 - j, i);
            }
        }
    }

    private void swap(int[][] matrix, int i1, int j1, int i2, int j2) {
        int tmp = matrix[i1][j1];
        matrix[i1][j1] = matrix[i2][j2];
        matrix[i2][j2] = tmp;
    }
}

4. 复杂度分析​

  • 时间复杂度：O(n²)，矩阵共有 n² 个元素，每组四个位置只处理一次。
  • 空间复杂度：O(1)，交换时只保存一个临时值。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明