题目链接
题目描述
给定一个 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]]
题解
使用辅助矩阵
虽然题目要求 原地 算法,不能使用辅助矩阵,我们为了更好的理解元素旋转前和旋转后的关系,先使用辅助矩阵实现旋转。
其实我们主要理解的是当前行 i
和当前列 j
在旋转后的变化关系,如上图,第一行旋转完后变成了倒数第一列,第二行旋转后变成了倒数第二列,依次类推。
对于 n x n
矩阵的一个元素 $matrix[i][j]$ 而言,旋转后列的值 j
转换成了行的值,旋转后列的值变成了倒数第 i
列,即 n - 1 - i
列。
我们假设
row
代表行,col
代表列,则可以总结出公式:
推出:$matrix[i][j] → matrix[j][n - i - 1]$
const rotate = (matrix) => {
const n = matrix.length;
const newMatrix = Array(n).fill(0).map(() => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
newMatrix[j][n - i -1] = matrix[i][j];
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix[i][j] = newMatrix[i][j];
}
}
}
复杂度分析:
- 时间复杂度:$O(n ^ 2)$
- 空间复杂度:因为需要使用
n x n
的辅助矩阵,故为 $O(n ^ 2)$
原地旋转
上一种方法之所以需要辅助矩阵来完成是因为都是整行转换成整列,如果使用这样的方式原地旋转第二行时最后一个元素的值就是已经不是原值了。
其实我们可以把一个 n x n
的矩阵分成四个区块,每次都将四个区块相对应位置的元素进行旋转互换即可,区块划分如下图:
当 n
为偶数时,需要枚举 $n ^ 2 / 4 = (n / 2) * (n / 2)$ 次,以 4 x 4
的矩阵为例。
当 n
为奇数时,需要枚举 $(n ^ 2 - 1) / 4 = ((n - 1) / 2) * ((n + 1) / 2)$,以 5 x 5
的矩阵为例,最中心的元素不需要遍历。
根据 和 可推导出每次遍历需要旋转的四个位置的元素如下:
- 左上区块:$matrix[i][j]$
- 右上区块:$matrix[j][n - i - 1]$
- 右下区块:$matrix[n - i - 1][n - j - 1]$
- 左下区块:$matrix[n - j - 1][i] = matrix[n - j - 1][n - (n - i - 1) - 1]$
找到了每次遍历四个元素的位置,则可以通过一个中间变量 tmp
帮助四个元素完成旋转互换,过程如下:
const rotate = (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 - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = tmp;
}
}
}
复杂度分析:
- 时间复杂度:枚举的子矩阵复杂度为 $O((n / 2) * ((n + 1) / 2))$,故为 $O(n ^ 2)$
- 空间复杂度:$O(1)$
上下翻转 + 左对角线翻转
其实 原地 算法不仅仅原地旋转一种方式,我们可以通过如下方式实现旋转 90
度的操作:
- 上下翻转 + 左对角线翻转
- 左对角线翻转 + 左右翻转
- 左右翻转 + 右对角线翻转
- 右对角线翻转 + 上下翻转
因为矩阵使用的数据结构是一个二维数组,所以为了便于程序的编写,我们选择先 上下翻转,再 左对角线翻转,过程如下图:
左对角线翻转的实现逻辑就是把第 i
行的第 j
列换到第 j
行的第 i
列,最重要的是要控制交换次数以防止重复交换。
遍历是从行开始的,应以 i
为基准,所以 j
的值一定要小于 i
,即列的遍历次数随着行的增加而递增。
const rotate = (matrix) => {
const n = matrix.length;
matrix.reverse();
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
}
复杂度分析:
- 时间复杂度:上下翻转的时间复杂度为 $O(n)$,对角线翻转的的时间复杂度为 $O(n ^ 2)$,故为 $O(n ^ 2)$
- 空间复杂度:$O(1)$