LeetCode 题解——旋转图像
大家好，我是前端西瓜哥。今天来做一道 medium 难度的 LeetCode 算法题：旋转图像。
废话不多说，我们直接看题目。
简单来说，就是要将一个从左往右从上到下的正方形矩阵，旋转 90 度，转换为从上往下从右往左的矩阵，且需要为原地算法，不使用额外的一个矩阵。
LeetCode 对应题目为：
- 《程序员面试金典（第 6 版）》面试题 01.07. 旋转矩阵：https://leetcode-cn.com/problems/rotate-matrix-lcci/
额外用一个矩阵
虽然题目要求不使用另一个矩阵，但我还是试着写了个额外用一个矩阵的解法。
因为如果题目没有做限制，这种写法是最容易想到且实现简单。
function rotate(matrix: number[][]): void { const n = matrix.length; // 初始化 const tmpMatrix = new Array(n); for (let i = 0; i < n; i++) { tmpMatrix[i] = new Array(n); } // 旋转 for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { tmpMatrix[j][n - 1 - i] = matrix[i][j] } } // 拷贝回去（浅拷贝） for (let i = 0; i < n; i++) { matrix[i] = tmpMatrix[i]; } }
首先是初始化一个大小和 matrix 一样的二维数组 tmpMatrix。
然后遍历 matrix 将其从上到下的每一行，对应到 ret 的从右往左的每一列里，对应关系为：tmpMatrix[j][n - 1 - i] = matrix[i][j]。
最后将 tmpMatrix 拷贝回 matrix。
就是这么简单。
时间复杂度 O(n^2)，空间复杂度 O(n^2)
从外到内一层层旋转
还有一种就是从最外层到最内层，一层层做旋转，就像剥洋葱一样。
function rotate(matrix: number[][]): void { const n = matrix.length; for (let i = 0, len = Math.floor(n / 2); i < len; i++) { // 一共有 n/2 层 const end = n - i - 1; // 结束的索引 for (let j = i; j < end - i; j++) { swap(matrix, i, j, j, end - i); swap(matrix, i, j, end - i, end - j); swap(matrix, i, j, end - j, i); } } }; function swap(matrix: number[][], a: number, b: number, c: number, d: number) { let tmp = matrix[a][b]; matrix[a][b] = matrix[c][d]; matrix[c][d] = tmp; // 或 js 特有的交换写法 // [matrix[a][b], matrix[c][d]] = [matrix[c][d], matrix[a][b]]; }
我们每次需要将上图中的这四个块做一个顺时针的依次交换。这里的难点在于找出四个点的对应关系。要找出这个规律，你要注意 i, j 的流向。对于特定的一圈，它的 i 是不变的，j 则是递增的。
假设我们用 matrix[x][y] 代表一个点，end 表示结束的索引的位置。
图中黄色部分从左往右，x 不变，y 增大，所以是 (i, j)；
橙色部分从上到下 x 增大，y 不变，但它在最右侧，所以是 (j, end - i)；
红色部分从右到左 x 变小，y 不变，但它在最下边，所以是 (end - i, end - j);
粉色部分从下往上 x 边小，y 不变且值等于 i，所以是 (end - j, i);
时间复杂度 O(n^2)，空间复杂度 O(1)。
对角线交换 + 左右交换（逆转）
这个实现就简单多了，其实就是将原本从左往右然后从上往下的顺序，先转换为从上往下然后从左往右的顺序，最后来一个倒转，变成从上往下然后从右往左。
function rotate(matrix: number[][]): void { // 对角线交换 const n = matrix.length; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { let tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } } // 左右交换 for (let i = 0; i < n; i++) { matrix[i].reverse(); } };
时间复杂度 O(n^2)，空间复杂度 O(1)。
总结
第一个解法是没有思路时，通过尝试解除不使用额外矩阵的限制来实现的，如果面试不做空间复杂度的限制，可以考虑用这个解法。
第二个解法则是从最外层到最内层一层层旋转的思路，这个思路是从 “旋转” 这个角度思考，但实现上四个点的对应关系很容易写错，慎用。
面试时遇到这道题建议用第三个解法，也就是最后一个解法，相对较好理解，也不容易写错。
