48. 旋转图像
题目描述
输入一个 n x n 的二维矩阵 matrix，它代表一幅图像。
把图像按顺时针方向转 90 度：原来的第一行变成最后一列，原来的最后一行变成第一列。
必须直接修改 matrix 本身，不能借助另一个矩阵。函数不返回值，判题检查修改后的 matrix。
示例 1
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
解释：第一行 [1,2,3] 转到了最后一列，第一列变成自下而上的 7,4,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]]
数据范围
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
解题思路：转置 + 行翻转
先沿主对角线转置，再将每一行反转。转置把行列交换，行反转正好完成顺时针方向。
为什么正确
转置后 matrix[i][j] 等于原 matrix[j][i]；行反转后每个元素到达顺时针旋转位置。
复杂度分析
时间 O(n²)，空间 O(1)。
易错点
先转置再反转行是顺时针；反转列会得到另一个方向。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def rotate(self, matrix):
n=len(matrix)
for i in range(n):
for j in range(i+1,n): matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
for row in matrix: row.reverse()class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
for (int[] row : matrix)
for (int a = 0, b = n - 1; a < b; a++, b--) {
int tmp = row[a];
row[a] = row[b];
row[b] = tmp;
}
}
}class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) swap(matrix[i][j], matrix[j][i]);
for (auto& row : matrix) reverse(row.begin(), row.end());
}
};func rotate(matrix [][]int) {
n := len(matrix)
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]
}
}
for _, row := range matrix {
for a, b := 0, n-1; a < b; a, b = a+1, b-1 {
row[a], row[b] = row[b], row[a]
}
}
}var rotate = function(matrix) {
const n = matrix.length;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++) [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
for (const row of matrix) row.reverse();
};function rotate(matrix: number[][]): void {
const n = matrix.length;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++) [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
for (const row of matrix) row.reverse();
};其他解法
辅助矩阵最直观但占 O(n²) 空间；四元素轮换和转置 + 行翻转都是原地 O(1) 空间，前者每个元素只移动一次，后者用两次简单翻转组合出旋转，更不易出错。
解法 2：辅助矩阵 时间 O(n²)，空间 O(n²)
顺时针旋转后，原来第 i 行第 j 列的元素会到第 j 行第 n-1-i 列。新建一个 n×n 矩阵，按 new[j][n-1-i] = matrix[i][j] 填入。最后把新矩阵逐个元素复制回原矩阵。
直接写出旋转的坐标公式，最容易验证。需要 O(n²) 额外空间，不满足原地要求，适合用来推导后两种原地做法。
class Solution:
def rotate(self, matrix):
n = len(matrix)
new = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
new[j][n - 1 - i] = matrix[i][j]
for i in range(n):
for j in range(n):
matrix[i][j] = new[i][j]class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] nw = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) nw[j][n - 1 - i] = matrix[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) matrix[i][j] = nw[i][j];
}
}class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> nw(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) nw[j][n - 1 - i] = matrix[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) matrix[i][j] = nw[i][j];
}
};func rotate(matrix [][]int) {
n := len(matrix)
nw := make([][]int, n)
for i := range nw {
nw[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
nw[j][n-1-i] = matrix[i][j]
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
matrix[i][j] = nw[i][j]
}
}
}var rotate = function(matrix) {
const n = matrix.length;
const nw = Array.from({length: n}, () => new Array(n).fill(0));
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) nw[j][n - 1 - i] = matrix[i][j];
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) matrix[i][j] = nw[i][j];
};function rotate(matrix: number[][]): void {
const n = matrix.length;
const nw: number[][] = Array.from({length: n}, () => new Array(n).fill(0));
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) nw[j][n - 1 - i] = matrix[i][j];
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) matrix[i][j] = nw[i][j];
}解法 3：四元素轮换 时间 O(n²)，空间 O(1)
由坐标公式可知，(i, j)、(j, n-1-i)、(n-1-i, n-1-j)、(n-1-j, i) 四个位置构成一个旋转环。用一个临时变量把这四个元素依次轮换一格。只需枚举左上角 n/2 × (n+1)/2 的区域，就能覆盖每个环恰好一次。
每个元素只移动一次，比转置 + 行翻转少一半的写操作。缺点是下标容易写错，枚举范围在 n 为奇数时需要特别注意。
class Solution:
def rotate(self, matrix):
n = len(matrix)
for i in range(n // 2):
for j in range((n + 1) // 2):
tmp = matrix[i][j]
matrix[i][j] = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = tmpclass Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
}class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
};func rotate(matrix [][]int) {
n := len(matrix)
for i := 0; i < n/2; i++ {
for j := 0; j < (n+1)/2; j++ {
tmp := matrix[i][j]
matrix[i][j] = matrix[n-1-j][i]
matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
matrix[j][n-1-i] = tmp
}
}
}var rotate = function(matrix) {
const n = matrix.length;
for (let i = 0; i < Math.floor(n / 2); i++) {
for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
const tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
};function rotate(matrix: number[][]): void {
const n = matrix.length;
for (let i = 0; i < Math.floor(n / 2); i++) {
for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
const tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}