题目描述#

给定一个 n x n 的二维矩阵 matrix，它表示一张图像。现在需要把这张图像顺时针旋转 90 度，并且要求在原地完成，不能额外创建一个同样大小的新矩阵。

这题的重点不只是“转过去”，而是要在不借助额外矩阵的前提下，直接修改原数组。

知识边界#

我一开始对“原地旋转矩阵”这件事的直觉并不强，尤其是不太容易一下子看出，为什么“先转置，再把每一行反转”就等价于顺时针旋转 90 度。

如果从坐标变化去看会更清楚一些。原来位置在 (i, j) 的元素，顺时针旋转后会到 (j, n-1-i)。而先做一次转置，会把它放到 (j, i)；再把第 j 行反转，就会到 (j, n-1-i)。这和目标位置完全一致，所以这两个操作连起来就等价于顺时针旋转。

另一个容易模糊的点是：转置时为什么内层循环只写 j < i。原因是对角线两侧的元素交换一次就够了，如果把整张矩阵都扫一遍，同一对位置会被交换两次，最后又回到原样。所以这里只遍历左下三角（或右上三角）即可。

另外，这份代码用了 slices.Reverse，这要求 Go 版本支持标准库里的 slices 包。如果环境比较旧，没有这个包，就需要自己写一个双指针反转。

思路#

这题可以拆成两步做。

第一步是矩阵转置。也就是把 matrix[i][j] 和 matrix[j][i] 交换。转置之后，原本的行会变成列，列会变成行，但这时图像还不是最终的顺时针旋转结果。

第二步是把转置后的每一行原地反转。这样一来，每一行里的元素顺序被调转，整个矩阵就变成了顺时针旋转 90 度之后的样子。

这种写法的好处是完全原地，不需要额外申请一个 n x n 的矩阵。时间复杂度是 O(n^2)，因为转置和逐行反转都要遍历矩阵中的元素；额外空间复杂度是 O(1)。

代码#

import "slices"

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 _, row := range matrix {
		slices.Reverse(row)
	}

}