48. 旋转图像
3 min
题目
解法：翻转转置
思路
核心思想：先上下翻转矩阵，再沿主对角线转置。 正确性：上下翻转将行顺序颠倒，转置实现行列互换，组合效果等价于顺时针旋转90度。数学上，旋转90度可分解为这两个线性变换：设原矩阵为M，上下翻转后为M’，转置后为M”，则M”=M^T·J（J为翻转矩阵），该变换与旋转操作等价。
- Step 1: 遍历前n/2行，交换第i行与第n-1-i行
- Step 2: 遍历矩阵上三角区域，交换matrix[i][j]与matrix[j][i]
复杂度
- 时间复杂度: ，需遍历整个矩阵两次，每层循环均为O(n)。
- 空间复杂度: ，仅使用常数级额外变量进行元素交换。
代码
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 = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};