48 旋转图像
官方题解已经说的非常详细
https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-100-liked
普通做法
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> newMatrix(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
newMatrix[j][n - 1 - i] = matrix[i][j];
}
}
matrix.assign(newMatrix.begin(),newMatrix.end());
}
};
原地旋转
方法一
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int row = 0; row < n / 2; row++) {
for (int col = 0; col < (n + 1) / 2; col++) {
int temp = matrix[row][col];
matrix[row][col] = matrix[n - 1 - col][row];
matrix[n - 1 - col][row] = matrix[n - 1 - row][n - 1 - col];
matrix[n - 1 - row][n - 1 - col] = matrix[col][n - 1 - row];
matrix[col][n - 1 - row] = temp;
}
}
}
};
复杂度分析
时间复杂度:\(O(N^2)\),其中 N 是 matrix 的边长。我们需要枚举的子矩阵大小为 \(O(⌊n/2⌋×⌊(n+1)/2⌋)=O(N^2 )\)。
空间复杂度:\(O(1)\)。为原地旋转。
方法二
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 (int j = 0; j < n / 2; j++) {
for (int i = 0; i < n; i++) {
swap(matrix[i][j], matrix[i][n - 1 - j]);
}
}
}
};
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
swap(matrix[i][j], matrix[j][i]);
}
}
for(int i = 0; i < n; i++){
int left = 0, right = n - 1;
while(left < right){
swap(matrix[i][left], matrix[i][right]);
left++;
right--;
}
}
}
};
复杂度分析
时间复杂度:\(O(N^2)\),其中 N 是 matrix 的边长。对于每一次翻转操作,我们都需要枚举矩阵中一半的元素。
空间复杂度:\(O(1)\)。为原地翻转得到的原地旋转。