421 lines
14 KiB
Markdown
421 lines
14 KiB
Markdown
---
|
||
tags: ["LeetCode", "矩阵", "中等"]
|
||
create time: 2026-05-17 15:00
|
||
---
|
||
|
||
# 20-旋转图像
|
||
|
||
## 题面
|
||
|
||
> **LeetCode 48. Rotate Image**
|
||
|
||
给定一个 `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`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 动手试试：把一张纸顺时针转 90°，原来在左上角的元素会去哪？
|
||
|
||
直观地想，如果把手机顺时针翻转 90°：
|
||
- 原来的**第一行** `[1, 2, 3]` 变成了**最后一列**（从下到上）
|
||
- 原来的**最后一行** `[7, 8, 9]` 变成了**第一列**（从上到下）
|
||
|
||
更精确地说——位置 `(i, j)` 的元素，旋转后会去往新位置 `(j, n-1-i)`。
|
||
|
||
| 原始位置 | 旋转后位置 |
|
||
|---------|-----------|
|
||
| (0, 0) | (0, 2) |
|
||
| (0, 1) | (1, 2) |
|
||
| (0, 2) | (2, 2) |
|
||
| (1, 0) | (0, 1) |
|
||
| **(1, 1)** | **(1, 1)** ← 中心不动 |
|
||
| (2, 0) | (0, 0) |
|
||
| (2, 1) | (1, 0) |
|
||
| (2, 2) | (2, 0) |
|
||
|
||
但直接用这个公式逐个搬运会很麻烦——因为你无法确定哪个是"已处理过的旧值"，会导致数据覆盖丢失。我们需要找一个**成对交换、自包含**的操作模式。
|
||
|
||
---
|
||
|
||
### 方法一：分层模拟法 —— 逐层旋转（O(1) 空间）⭐⭐⭐
|
||
|
||
> [!question] 💡 分解问题：n×n 矩阵可以看作多少个嵌套的「边框」？
|
||
|
||
以 4×4 为例，想象一个俄罗斯套娃：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["4×4 矩阵"] --> B["第 0 层：最外层边框 12 个元素参与旋转"]
|
||
B --> C["第 1 层：内层 2×2 边框 4 个元素参与旋转"]
|
||
C --> D(["完成"])
|
||
|
||
style A fill:#e1f5fe
|
||
style B fill:#fff3e0
|
||
style C fill:#f3e5f5
|
||
style D fill:#e8f5e9
|
||
```
|
||
|
||
每一层的四个边上，对应位置的四个元素互相轮换：
|
||
|
||
```
|
||
A → B
|
||
↓ ↓
|
||
D ← C
|
||
|
||
轮换关系：A→B→C→D→A （顺时针移动）
|
||
```
|
||
|
||
> [!abstract] 🗺️ 核心观察：四个角组成一个循环
|
||
|
||
对于第 `layer` 层（从外往里数），遍历该层的每一条边（但不包括最后一个点，因为那是第四个角，会被自动补齐）。每次取一条边上相邻的四个对应位置：
|
||
|
||
```
|
||
(layer, j) → 顶部
|
||
↓ |
|
||
(n-1-j, layer) | 左侧
|
||
↑ |
|
||
| ↓
|
||
(n-1-layer, n-1-j) → 底部
|
||
|
||
↻ 顺时针四向互换
|
||
```
|
||
|
||
具体映射：设当前在第 `layer` 层的第 `offset` 个位置：
|
||
|
||
| 角色 | 坐标 | 含义 |
|
||
|------|------|------|
|
||
| 上 | `(layer, layer + offset)` | 上边 |
|
||
| 右 | `(layer + offset, n - 1 - layer)` | 右边 |
|
||
| 下 | `(n - 1 - layer, n - 1 - layer - offset)` | 下边 |
|
||
| 左 | `(n - 1 - layer - offset, layer)` | 左边 |
|
||
|
||
四个位置的值做环形交换：`top → right → bottom → left → top`
|
||
|
||
> [!step] 算法流程
|
||
|
||
```mermaid
|
||
flowchart TB
|
||
Start(["开始"]) --> InitLayers["① layer = 0, 最外层"]
|
||
InitLayers --> CountOffset["② 每层 offset 范围：0 ~ (n-1-2*layer)-1"]
|
||
CountOffset --> QuadLoop["③ 对每个 offset，取四对元素做环形交换"]
|
||
QuadLoop --> NextLayer{"layer++ < n/2?"}
|
||
NextLayer -->|"是"| InitLayers
|
||
NextLayer -->|"否"| Return(["返回结果"])
|
||
```
|
||
|
||
1. 外层循环：`layer` 从 0 到 `n/2 - 1`（共有 ⌊n/2⌋ 层）
|
||
2. 内层循环：`offset` 从 0 到 `(n - 1 - 2*layer) - 1`
|
||
3. 每个 `(layer, offset)` 找到四个对应位置，用临时变量做 3 次 swap 完成环形交换
|
||
|
||
> [!example] 🔍 逐步跟踪演示
|
||
|
||
以 3×3 矩阵为例：
|
||
|
||
```
|
||
[[1, 2, 3], layer=0
|
||
[4, 5, 6], n = 3, n/2 = 1, 只有 1 层
|
||
[7, 8, 9]]
|
||
```
|
||
|
||
**layer = 0, offset = 0:**
|
||
- 上: `(0, 0) = 1`
|
||
- 右: `(0, 2) = 3`
|
||
- 下: `(2, 2) = 9`
|
||
- 左: `(2, 0) = 7`
|
||
|
||
四向交换：`1→右, 3→下, 9→左, 7→上` → 上得 7, 右得 1, 下得 3, 左得 9
|
||
|
||
```
|
||
[[7, 2, 1],
|
||
[4, 5, 6],
|
||
[9, 8, 3]]
|
||
```
|
||
|
||
**layer = 0, offset = 1:**
|
||
- 上: `(0, 1) = 2`
|
||
- 右: `(1, 2) = 6`
|
||
- 下: `(2, 1) = 8`
|
||
- 左: `(2, 0) = 9` — 等等，(2,0) 已经被改成了 9...
|
||
|
||
让我重新理清：我们用临时变量暂存，而不是连续写入同一个位置：
|
||
|
||
```
|
||
temp = matrix[0][0] = 1 // 暂存"上"
|
||
matrix[0][0] = matrix[2][0] = 7 // 左→上
|
||
matrix[2][0] = matrix[2][2] = 9 // 下→左
|
||
matrix[2][2] = matrix[0][2] = 3 // 右→下
|
||
matrix[0][2] = temp = 1 // 上→右
|
||
```
|
||
|
||
得到：
|
||
```
|
||
[[7, 2, 1],
|
||
[4, 5, 6],
|
||
[9, 8, 3]]
|
||
```
|
||
|
||
**layer = 0, offset = 1:**
|
||
- 上: `(0, 1) = 2`
|
||
- 右: `(1, 2) = 6`
|
||
- 下: `(2, 1) = 8`
|
||
- 左: `(1, 0) = 4`
|
||
|
||
```
|
||
temp = 2, matrix[0][1] = 4, matrix[1][0] = 8, matrix[1][2] = 2, matrix[2][1] = 6
|
||
```
|
||
|
||
得到：
|
||
```
|
||
[[7, 4, 1],
|
||
[8, 5, 2],
|
||
[9, 6, 3]]
|
||
```
|
||
|
||
完成！✅
|
||
|
||
> [!note] 📌 复杂度分析
|
||
|
||
| 维度 | 复杂度 | 说明 |
|
||
|------|--------|------|
|
||
| 时间 | O(n²) | 共 n²/2 个需要移动的元素，每个常数次操作 |
|
||
| 空间 | **O(1)** | 只用一个临时变量 `temp` |
|
||
|
||
> [!quote] ❌ 评价
|
||
|
||
这种方法直接模拟题目要求，逻辑清晰且最优。但在实现时需要仔细推导四个方向的坐标公式，容易出错。面试中如果时间充裕可以尝试，但需要足够的耐心调试坐标。
|
||
|
||
---
|
||
|
||
### 方法二：先转置再翻转 —— 两步操作法 ⭐⭐⭐（推荐）
|
||
|
||
> [!question] 💡 还记得我们之前讨论的矩阵转置吗？转置是把行列互换，那转置后再做些调整，能不能凑出旋转效果？
|
||
|
||
这是面试中最推荐的解法，因为它把旋转拆解为两个极其简单的子问题：
|
||
|
||
> [!abstract] 🎯 核心洞察
|
||
|
||
**旋转 90° = 沿主对角线转置 + 左右翻转每行**
|
||
|
||
让我们验证一下：
|
||
|
||
```
|
||
原始矩阵 转置后 每行左右翻转
|
||
[[1,2,3]] [[1,4,7]] [[7,4,1]]
|
||
[[4,5,6]] → [[2,5,8]] → [[8,5,2]]
|
||
[[7,8,9]] [[3,6,9]] [[9,6,3]]
|
||
```
|
||
|
||
与目标输出一致 ✅
|
||
|
||
> [!question] 💡 为什么会这样？从几何角度理解
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["原始矩阵<br/>按左上↘右下对角线对称"] --> B["转置：<br/>row↔col 互换"]
|
||
B --> C["左右翻转<br/>每行的首尾对调"]
|
||
C --> D["顺时针旋转 90°"]
|
||
|
||
style A fill:#e1f5fe
|
||
style B fill:#fff3e0
|
||
style C fill:#f3e5f5
|
||
style D fill:#e8f5e9
|
||
```
|
||
|
||
**直觉解释：**
|
||
1. **转置**相当于沿对角线折叠翻折（mirror across main diagonal）
|
||
2. **左右翻转**相当于垂直轴镜像（mirror across vertical midline）
|
||
3. 两次镜像 = 一次旋转（在二维空间中，两次正交反射等价于旋转 180° 的一部分；这里是 90°，因为两条镜面夹角为 45°）
|
||
|
||
> [!tip] 变体记忆法
|
||
|
||
如果你想不起来是"先转置再左右翻转"还是"先上下翻转再左右转置"，记住：
|
||
|
||
| 变换组合 | 结果 |
|
||
|---------|------|
|
||
| **转置 + 左右翻转** | 顺时针旋转 90° |
|
||
| 转置 + 上下翻转 | 逆时针旋转 90° |
|
||
| 上下翻转 + 左右转置 | 顺时针旋转 90° |
|
||
|
||
只要记住一组就够了，另一组作为验证。
|
||
|
||
> [!step] 算法流程
|
||
|
||
**Step ①：转置（Transpose）**
|
||
|
||
遍历主对角线上方的所有元素 `(i, j)`（其中 `i < j`），交换 `matrix[i][j]` 和 `matrix[j][i]`：
|
||
|
||
```go
|
||
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]
|
||
}
|
||
}
|
||
```
|
||
|
||
注意这里只需要遍历 `j > i` 的区域（上三角），避免重复交换回去。
|
||
|
||
**Step ②：每行左右翻转（Reverse Each Row）**
|
||
|
||
```go
|
||
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]
|
||
}
|
||
}
|
||
```
|
||
|
||
每行只需翻转一半长度。
|
||
|
||
```mermaid
|
||
flowchart TB
|
||
Start(["开始"]) --> Transpose["① 沿主对角线转置<br/>遍历上三角区域 i<j"]
|
||
Transpose --> ReverseRows["② 每行左右翻转<br/>头尾配对交换"]
|
||
ReverseRows --> Return(["返回结果"])
|
||
```
|
||
|
||
> [!note] 📌 复杂度分析
|
||
|
||
| 维度 | 复杂度 | 说明 |
|
||
|------|--------|------|
|
||
| 时间 | O(n²) | 转置 O(n²/2) + 翻转 O(n²/2)，总计 O(n²) |
|
||
| 空间 | **O(1)** | 仅用交换时的临时变量 |
|
||
|
||
> [!success] ✅ 为什么推荐这个方法？
|
||
|
||
- **代码极其简洁**——每步都只有一个双循环，不易出错
|
||
- **易验证正确性**——可以单独测试转置和翻转的正确性
|
||
- **面试友好**——可以先写出转置，再引导面试官推导出"加上翻转就完成了"
|
||
- **扩展性强**——同样的思路可以推广到旋转 180°（两次转置=不变，所以需要两次翻转）、逆时针 90°（转置+上下翻转）等变体
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
> [!abstract] 📝 伪代码框架（先转置再翻转）
|
||
|
||
```
|
||
// ── Step 1: 沿主对角线转置 ──
|
||
for i 从 0 到 n-1:
|
||
for j 从 i+1 到 n-1:
|
||
交换 matrix[i][j] 和 matrix[j][i]
|
||
|
||
// ── Step 2: 每行左右翻转 ──
|
||
for i 从 0 到 n-1:
|
||
for j 从 0 到 n/2-1:
|
||
交换 matrix[i][j] 和 matrix[i][n-1-j]
|
||
```
|
||
|
||
> [!warning] ⚠️ Go 实现中的常见坑
|
||
|
||
1. **善用 Go 的多重赋值做 swap**——`a, b = b, a` 简洁且安全，不需要显式声明 `temp` 变量。
|
||
2. **不要写两层独立的 `0..n-1` 转置循环**——那样会把已经交换过的元素再换回来，等于没做。必须限制 `j > i`（只遍历上三角或下三角）。
|
||
3. **边界情况 n=1**——两层循环都不会进入，直接返回原矩阵，符合预期（1×1 矩阵旋转不变）。
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：镜像-旋转对偶性（Mirror-Rotation Duality）
|
||
|
||
在二维矩阵的原地变换中，**多次镜像反射可以组合成任意旋转/翻转**。这是因为正交群 O(2) 中的任意旋转可以由至多两次反射生成。这一性质让复杂的空间变换被拆成了简单、可验证的基础操作。
|
||
|
||
> [!note] 🐹 Go 语言中的注意事项
|
||
|
||
- Go 的切片交换 `a, b = b, a` 是原子性的——右侧全部求值后才左侧赋值，不会像 C 那样产生中间状态。
|
||
- 对于固定大小的矩阵，可以直接访问 `matrix[i][j]`，无需 range 迭代器。
|
||
- 如果需要打印调试，可以用双重循环格式化输出，注意对齐宽度。
|
||
|
||
> [!info] 📊 两种最优解对比
|
||
|
||
| 维度 | 逐层模拟法 | 转置+翻转法 ⭐ |
|
||
|------|-----------|-------------|
|
||
| 代码量 | ~15 行（坐标公式多） | ~8 行（两个简单循环） |
|
||
| 出错概率 | 较高（4 个方向坐标容易写错） | 极低（转置和翻转都是基础操作） |
|
||
| 理解难度 | 需要想象四层轮换 | 只需理解两次简单变换 |
|
||
| 面试表现 | 展示深度，但耗时 | 快速交付正确解，留时间讨论扩展 |
|
||
|
||
> [!quote] 💬 思维延伸
|
||
|
||
这道题教会了我们一个重要的解题策略：**把复杂的复合变换拆解为基础操作序列**。类似的思想出现在：
|
||
- 图片编辑软件中的滤镜链（灰度 → 对比度 → 锐化）
|
||
- SVG/CSS 动画中的 transform 组合（rotate + scale + translate）
|
||
- 计算机图形学中的 MVP 矩阵（Model → View → Projection）
|
||
|
||
当你面对一个复杂的几何变换问题时，问自己：
|
||
|
||
> 能不能把它拆成两个或多个「明显正确的」简单步骤？
|
||
|
||
这种"组合子思维"（combinator design）在很多算法题中都奏效——比如反转链表可以先分成"前驱-后继指针三指针"两两交换，排序可以先分成"分组后组内排序再合并"。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
// rotateMatrix 将 n×n 矩阵顺时针旋转 90 度。
|
||
// 使用原地算法：先沿主对角线转置，再翻转每一行。
|
||
// 时间 O(n²)，空间 O(1)。
|
||
func rotate(matrix [][]int) {
|
||
n := len(matrix)
|
||
|
||
// ═══ Step 1: 沿主对角线转置（交换上三角和下三角） ═══
|
||
// 只遍历 j > i 的区域，确保每个元素对被交换恰好一次
|
||
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]
|
||
}
|
||
}
|
||
|
||
// ═══ Step 2: 每行左右翻转 ═══
|
||
// 每行仅需翻转前半部分与后半部分的对应元素
|
||
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]
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
|
||
这是 LeetCode 第 48 题，通过率约 75%，是一道经典的 **矩阵原地变换** 面试题。
|
||
|
||
- **运行时间**：约 0~3 ms（Go，击败 ~99%+ 提交）
|
||
- **空间消耗**：O(1) 额外空间
|
||
- **面试表现**：极高。这道题的代码极其简洁，面试官通常会在正确性确认后立即追问扩展：
|
||
- 如何逆时针旋转 90°？（转置 + 上下翻转）
|
||
- 如何旋转 180°？（两次左右翻转 / 两次上下翻转）
|
||
- 如果是 m×n 的非方阵怎么办？（无法原地旋转，需要额外空间）
|
||
- 如果要求不修改矩阵呢？（用坐标映射公式计算原始索引）
|
||
|
||
> [!quote] 💬 延伸思考
|
||
|
||
> 当你觉得某个操作很复杂时，很可能只是还没找到合适的坐标系。
|
||
|
||
旋转 90° 的本质是坐标映射 `(i, j) → (j, n-1-i)`。但这个公式直接实现的代价高——它需要知道哪些位置"已经被新值污染"了。而如果我们换个视角，发现**转置+翻转**在数学上等价于这个映射，那么代码就从"追踪每个元素的去向"简化成了"两个独立的线性扫描"。
|
||
|
||
记住这句口诀：**"一转二翻"** —— 先转置、再翻转。下次遇到旋转矩阵的题目，条件反射即可写出最优解。
|