LeetCode 48 - 旋转图像（Rotate Image）

问题描述

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

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

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]

旋转前：

1
2
3

1 2 3
4 5 6
7 8 9

旋转后：

1
2
3

7 4 1
8 5 2
9 6 3

示例 2：

1 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]]

旋转前：

 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

解题思路

旋转图像是一个经典的矩阵操作问题。关键在于：如何在不使用额外空间的情况下完成矩阵的旋转。

首先，让我们理解一下顺时针旋转 90 度对矩阵元素位置的影响：

对于位置 (i, j) 的元素，旋转后它将位于 (j, n-1-i)

这个规律可以帮助我们直接交换元素，但直接这样操作会导致覆盖其他元素。因此，我们可以采用分解为多个简单变换的方法。

方法：转置 + 水平翻转

这个方法将 90 度旋转分解为两个简单的矩阵操作：

矩阵转置（沿主对角线翻转）
水平翻转（左右列交换）

步骤详解：

矩阵转置：
- 遍历矩阵的一半（对角线以下部分），交换 matrix[i][j] 和 matrix[j][i]
- 这一步将行变为列，列变为行
水平翻转：
- 对每一行进行左右翻转
- 将第 j 列和第 n-1-j 列交换

这两步操作组合起来，正好等同于将矩阵顺时针旋转 90 度。

我们可以通过一个例子来说明这个过程：

原始矩阵：

1
2
3

1 2 3
4 5 6
7 8 9

转置后：

1
2
3

1 4 7
2 5 8
3 6 9

水平翻转后：

1
2
3

7 4 1
8 5 2
9 6 3

可以看到，最终结果正是原矩阵顺时针旋转 90 度后的结果。

实现细节

实现过程中，需要注意以下几点：

在转置操作中，我们只需要遍历矩阵的一半（主对角线以下的部分），避免重复交换
在水平翻转中，只需要遍历每行的前一半列
所有操作都是原地进行的，不需要额外的空间

代码实现

func rotate(matrix [][]int) {
	// 先沿着主对角线进行对称反转
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}

	// 然后每一行进行水平翻转
	for i := 0; i < n; i++ {
		for j := 0; j < n/2; j++ {
			matrix[i][n-1-j], matrix[i][j] = matrix[i][j], matrix[i][n-1-j]
		}
	}
}

复杂度分析

时间复杂度：O(n²)，其中 n 是矩阵的边长。需要遍历整个矩阵两次。
空间复杂度：O(1)，只使用了常数级别的额外空间。

其他可能的方法

除了上述方法外，还有另一种旋转方法：层层旋转。

此方法的思路是：

将矩阵看作由多个同心方形环组成
对每一层的四条边上的元素进行旋转交换
从外到内依次处理每一层

代码实现会稍微复杂一些，需要小心处理索引，但时间和空间复杂度与上述方法相同。

比较

方面	转置+水平翻转	层层旋转
时间复杂度	O(n²)	O(n²)
空间复杂度	O(1)	O(1)
优点	实现简单，思路清晰	直观对应旋转过程
缺点	分解为两步不直观	索引处理复杂
推荐度	★★★★★	★★★☆☆

关键收获

矩阵操作的分解思想：将复杂的矩阵操作分解为简单操作的组合
原地算法的实现技巧：如何通过元素交换实现空间优化
矩阵转置和水平翻转：这是两个常用的矩阵操作，在其他问题中也经常用到

对于矩阵旋转问题，关键是找到元素变换前后位置的对应关系，然后利用这种关系设计高效的算法。