48. Rotate Image.md

48. Rotate Image

思路

题目要求顺时针翻转一个用二维数组表示的图像，要求空间复杂度O(1)。
将图像进行旋转有一点像转置操作，如果这题想到转置的话就简单了，我们来看一个例子:

 1 2 3                1 4 7             7 4 1
 4 5 6  --transpose-> 2 5 8 --reverse-> 8 5 2
 7 8 9                3 6 9             9 6 3

我们知道，对矩阵进行转置操作就是对其沿对角线作一个交换操作，即swap(matrix[i][j], matrix[j][i])，所以这很好实现，而从转置后的矩阵得到 最终的翻转矩阵只需将每一行进行reverse就可以了。整个过程都是in-place的，不需要额外分配空间，满足题意。
时间复杂度O(n^2)，空间复杂度O(1)

思考：如果题目要求是逆时针旋转呢？
其实是类似的，也是先转置再反转，只是反转是对每列进行翻转的。

C++

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 i = 0; i < n; i++) reverse(matrix[i].begin(), matrix[i].end());
    }
};