本文概览：本文以LeetCode经典题目"旋转图像"为例，讲解两种解法：逐层四元素交换法和转置+翻转法，重点讲解逐层旋转时如何找到层数、每层元素个数以及索引的书写规律

一、题目

旋转图像题目

二、题目分析

给定一个 n×n 的二维矩阵表示一个图像，将图像顺时针旋转 90 度，要求原地旋转

目标：不使用额外矩阵，原地完成顺时针 90 度旋转

核心问题：如何找到旋转后每个元素的目标位置，以及如何原地完成交换

思路概览

本题有两种解法思路：

  • 方法一：逐层四元素交换——思路清晰直观，但代码实现较复杂，索引容易写错
  • 方法二：转置+翻转——思路比较绕，但代码实现简单很多

方法一：逐层四元素交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void rotate(int[][] matrix) {
    // 记录矩阵原始长度
    int n = matrix.length;
    // 遍历次数（层数）
    int layer = n / 2;
    // 每次旋转元素个数
    int count = n - 1;
    for (int i = 0; i < layer; i++) {
        // i为每次遍历的层号
        for (int j = 0; j < count; j++) {
            // 记录右上元素
            int temp1 = matrix[i + j][n - 1 - i];
            // 左上赋值右上
            matrix[i + j][n - 1 - i] = matrix[i][i + j];
            // 记录右下元素
            int temp2 = matrix[n - 1 - i][n - 1 - i - j];
            // 右上赋值右下
            matrix[n - 1 - i][n - 1 - i - j] = temp1;
            // 记录左下元素
            temp1 = matrix[n - 1 - i - j][i];
            // 右下赋值左下
            matrix[n - 1 - i - j][i] = temp2;
            // 左下赋值左上
            matrix[i][i + j] = temp1;
        }
        count -= 2;
    }
}

思路简要说明：

  1. 按层旋转：从外到内，每一层独立旋转，层数为 n/2
  2. 四元素交换：每一层内，将四个对应位置的元素循环交换——左上→右上→右下→左下→左上
  3. 元素个数递减：外层有 n-1 个元素需要旋转，每往内一层减少 2 个

方法二：转置+翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void rotate(int[][] matrix) {
    int n = matrix.length;

    // 第一步：转置（沿主对角线翻转，行变列、列变行）
    for (int i = 0; i < n; i++) {
        // j从i+1开始，避免重复交换和对角线元素与自己交换
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    // 第二步：上下翻转（第i行和第n-1-i行交换）
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - 1 - i][j];
            matrix[n - 1 - i][j] = temp;
        }
    }
}

思路简要说明：

  1. 第一步转置：沿主对角线翻转，行变列、列变行
  2. 第二步上下翻转：第 i 行和第 n-1-i 行交换
  3. 两步合在一起：(row, col) → (col, row) → (col, n-1-row)，恰好等于顺时针旋转 90 度

三、思路详解

方法一：逐层四元素交换

从外到内按层观察旋转

我们换一个视角来看旋转：不是逐个元素看它去了哪里，而是从外到内按层来看

一个 n×n 的矩阵可以看成若干层嵌套的正方形。最外面是一层，往内又是一层，直到中心。旋转的时候，每一层的元素都在自己的层内旋转，不会跑到其他层去

用一个 5×5 的矩阵来直观感受层的概念：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
┌─────────────────────┐ ← 外层（第0层）
│  1   2   3   4   5  │
│  6               10 │
│  11              15 │
│  16              20 │
│  21  22  23  24  25 │
└─────────────────────┘
   ┌─────────────┐    ← 内层（第1层）
   │  7   8   9   │
   │  12      14  │
   │  17  18  19  │
   └─────────────┘
        ┌─────┐      ← 最内层（第2层）
        │  13 │
        └─────┘

外层有 16 个元素需要旋转，内层有 8 个，最内层只有 1 个（即中心点 13，n 为奇数时不旋转）

所以我们可以一层一层地处理，外层处理完再处理内层，每一层的旋转规律是一模一样的

每一层的旋转规律

在每一层内，顺时针旋转 90 度，其实就是四个对应位置的元素循环替换：左上换到右上，右上换到右下，右下换到左下，左下换到左上

以上面 5×5 矩阵的外层为例：

1
2
3
4
5
6
旋转前：                    旋转后：
  1   2   3   4   5          21  16  11   6   1
  6               10         22               2
  11              15    →    23               3
  16              20         24               4
  21  22  23  24  25         25  20  15  10   5

外层的四个角 1、5、25、21 形成循环替换：1→右上、5→右下、25→左下、21→左上。中间的元素也是同样的规律

层数怎么确定？

既然是从外到内按层处理，那一共需要旋转多少层？

  • n 为奇数时：最中心有一个元素不需要旋转，层数 = n/2（向下取整，自动忽略中心点）
  • n 为偶数时：没有中心点，最内层是一个 2×2 的小方块，层数 = n/2

所以无论奇偶，层数都是 n/2

每层需要旋转多少个元素？

最外层有 n-1 个元素需要旋转（不是 n 个，因为第 n 个元素会和第一个重复）。每往内一层，边长减少 2，所以元素个数也减少 2

层号 i 元素个数
0（最外层） n-1
1 n-3
2 n-5
... ...

索引的书写规律

这是逐层交换法最容易出错的地方。我们来仔细分析

在内循环中，j 表示当前元素在该层内的偏移量。我们需要找到四个位置的索引与 i（层号）和 j（偏移）的关系

先看不变的规律：

  • 顶层的行索引始终是 i，不随 j 变化
  • 左层的列索引始终是 i，不随 j 变化
  • 右层的列索引始终是 n-1-i，不随 j 变化
  • 底层的行索引始终是 n-1-i，不随 j 变化

再看随 j 变化的规律：

  • 顶层的列索引和右层的行索引变化一致，都是由小到大，从 i 开始加 j
  • 左层的行索引和底层的列索引变化一致，都是由大到小，从 n-1-i 开始减 j

整理成表格：

位置 行索引 列索引
左上 i i + j
右上 i + j n - 1 - i
右下 n - 1 - i n - 1 - i - j
左下 n - 1 - i - j i

对照表格写索引，就不容易出错了

举例说明

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

层数 = 3/2 = 1，只旋转一层

外层元素个数 = 3-1 = 2，即 j=0 和 j=1

j=0 时（四个角）：

位置 索引 值
左上 [0][0] 1
右上 [0][2] 3
右下 [2][2] 9
左下 [2][0] 7

交换：1→右上位置，3→右下位置，9→左下位置，7→左上位置

j=1 时（四条边的中点）：

位置 索引 值
左上 [0][1] 2
右上 [1][2] 6
右下 [2][1] 8
左下 [1][0] 4

交换：2→右上位置，6→右下位置，8→左下位置，4→左上位置

最终结果为 [[7,4,1],[8,5,2],[9,6,3]]，正确

  • 时间复杂度：O(n²)，每个元素被访问一次
  • 空间复杂度：O(1)，原地交换

方法二：转置 + 上下翻转

思路分析

逐层交换法虽然思路清晰，但索引容易写错。有没有更简单的方法？

我们取矩阵中任意一个元素 (row, col)，顺时针旋转 90 度后它的新位置是 (col, n-1-row)

如何通过两步操作实现这个变换？

第一步：转置（沿主对角线翻转）

转置就是将 (row, col) 变成 (col, row)，即行变列、列变行

第二步：上下翻转

翻转就是将 (col, row) 变成 (col, n-1-row)

两步合在一起：(row, col) → (col, row) → (col, n-1-row)，正好就是旋转 90 度后的位置！

为什么上下翻转恰好是 n-1-row？因为 row + (n-1-row) = n-1，即翻转前后行号之和为 n-1，这就是上下翻转的定义

举例说明

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

第一步：转置

1
2
3
1  2  3      1  4  7
4  5  6  →   2  5  8
7  8  9      3  6  9

第二步：上下翻转

1
2
3
1  4  7      3  6  9
2  5  8  →   2  5  8
3  6  9      1  4  7

最终结果为 [[7,4,1],[8,5,2],[9,6,3]]，正确

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void rotate(int[][] matrix) {
    int n = matrix.length;

    // 第一步：转置（沿主对角线翻转，行变列、列变行）
    for (int i = 0; i < n; i++) {
        // j从i+1开始，避免重复交换和对角线元素与自己交换
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    // 第二步：上下翻转（第i行和第n-1-i行交换）
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - 1 - i][j];
            matrix[n - 1 - i][j] = temp;
        }
    }
}
  • 时间复杂度：O(n²)，转置和翻转各遍历一次
  • 空间复杂度：O(1)，原地交换