LeetCode Notes_面试题 01.07. 旋转矩阵
Contents
题目
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 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]
]解答
方法1：使用额外空间
创建一个新的矩阵newMatrix，按照旋转90度的方式把原矩阵的每个元素放入新矩阵。
在纸上写出新旧矩阵元素坐标，不难发现坐标的对应关系，
newMatrix[j][n - 1 - i] = matrix[i][j];注意，本题给出的函数签名没有返回值，所以还需要将newMatrix赋值回原矩阵。
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] newMatrix = new int[n][n];
for(int i = 0;i <= n - 1;i++){
for(int j = 0;j <= n - 1;j++){
newMatrix[j][n - 1 - i] = matrix[i][j];
}
}
for(int i = 0;i <= n - 1;i++){
for(int j = 0;j <= n - 1;j++){
matrix[i][j] = newMatrix[i][j];
}
}
}
}复杂度分析
时间复杂度：O(n2)
空间复杂度：O(n2)
方法2：先转置，再对每行中点翻转
分为两个步骤，代码看上去会很清晰。
- 首先沿着左上-右下对角线进行翻转，其实就相当于矩阵的转置。转置过后，变成了这样：
[1,4,7] [7,4,1]
[2,5,8] ---------> [2,5,8]（观察发现，还需要左右对称翻转）
[3,6,9] [3,6,9]- 观察转置之后的矩阵和目标矩阵的差距，如上，可以发现我们再进行一次左右对称的翻转，就可以得到目标矩阵了。
[7,4,1]
[8,5,2]
[9,6,3]class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for(int i = 0;i <= n - 1;i++){
for(int j = i + 1;j <= n - 1;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
//位运算右移一位，其实就是除以2的意思
int mid = n >> 1;
for(int i = 0;i <= n - 1;i++){
//这里的循环边界条件，一定要在纸上举例子验证，很容易搞错
for(int j = 0;j <= mid - 1;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
}复杂度分析
时间复杂度：O(n2)
空间复杂度：O(1),没有借助额外变量
方法3： 矩阵分为四块并进行顺时针旋转
这个方法比较抽象，但是理解之后，代码写起来很简单。以下有一个很清晰的图解。
- 首先我们可以将整个矩阵分解为四块，即左上，右上，左下，右下。我们发现其实旋转90度时，这四块当中的对应元素（也就是图中颜色相同的元素）进行了一次旋转。
- 然后我们可以观察出这些对应元素之间的坐标关系
- 左上角元素坐标（i,j）
- 右上角元素坐标（j, n - 1 - i）
- 右下角元素坐标（n - 1 - i, n - 1- j）
- 左下角元素坐标（n - 1 - j, i）
需要注意的是矩阵行列数为奇数的情况，左上角区域并不是整个矩阵的四分之一。
class 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 temp = 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] = temp;
}
}
}
}复杂度分析
时间复杂度：O(n2)
空间复杂度：O(1),没有借助额外变量