rotateImage

48. 旋转图像

分析

转置矩阵：
- 遍历上三角区域 (i, j) ，交换每对对称元素 matrix[i][j] 和 matrix[j][i]
水平翻转矩阵：
- 遍历每一行，交换每行左右两端对称的元素

时间复杂度

转置矩阵需要 O(n^2)
水平翻转需要 O(n^2)

总时间复杂度 O(n^2)

空间复杂度

在原地修改矩阵，空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution
{
public:
    void rotate(vector<vector<int>>& matrix)
    {
        int n = matrix.size();

        // 1. 转置矩阵
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                std::swap(matrix[i][j], matrix[j][i]);

        // 2. 水平翻转矩阵
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n / 2; ++j)
                std::swap(matrix[i][j], matrix[i][n - 1 - j]);
    }
};