链接
[https://leetcode-cn.com/problems/rotate-matrix-lcci/]
描述
给你一幅由 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 辅助数组
我们使用一个与 matrix 大小相同的辅助数组 {matrix_new临时存储旋转后的结果。我们遍历 matrix 中的每一个元素，根据上述规则将该元素存放到 }matrix_new中对应的位置。在遍历完成之后，再将matrix_new中的结果复制到原数组中即可。
c++
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组
auto matrix_new = matrix;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix_new[j][n - i - 1] = matrix[i][j];
}
}
// 这里也是值拷贝
matrix = matrix_new;
}
};
//时间复杂度：O(N^2),N是matrix的边长
//空间复杂度：O(N^2)，需要一个和matrix的大小相同的辅助数组
法2 原地旋转
考虑用一个临时变量temp暂存matrix的值
**.. ..** .... ....
**.. =下一项=> ..** =下一项=> .... =下一项=> ....
.... .... ..** **..
.... .... ..** **..
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 temp=matrix[i][j];
matrix[i][j]=matrix[n-1-j][i];
matrix[n-1-j][i]=matrix[n-i-1][n-1-j];
matrix[n-i-1][n-1-j]=matrix[j][n-1-i];
matrix[j][n-1-i]=temp;
}
}
}
};
//时间复杂度O（n^2)
//空间复杂度O（1），原地旋转
法3 旋转
5 1 9 11 15 14 12 16
2 4 8 10 13 3 6 7
------------ =水平翻转=> ------------
13 3 6 7 2 4 8 10
15 14 12 16 5 1 9 11
15 14 12 16 15 13 2 5
13 3 6 7 =主对角线翻转=> 14 3 4 1
2 4 8 10 12 6 8 9
5 1 9 11 16 7 10 11
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; ++j) {
swap(matrix[i][j], matrix[n - i - 1][j]);
}
}
// 主对角线翻转
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};