48. Rotate Image

题目描述：给一个n * n的二维数组表示的图片，将其原地顺时针旋转90度。如：

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

分析：如果可以重新申请一个 n * n 的矩阵，则分析元素变换前后的位置关系可得：
A[ i ][ j ] <——> A[ j ][ n - 1 - i]，代码如下：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> v(n);       //vector必须先指明其大小才能用下标赋值，这一步只指明了一层
        for (int i = 0; i < n ; i ++)
            v[i].resize(n);              //每层大小为n
        
        for (int i = 0; i < n ; i ++)
        {
            for (int j = 0; j < n ; j ++)
                v[j][n - 1 - i] = matrix[i][j];
        }
        
        for (int i = 0; i < n ; i ++)
        {
            for (int j = 0; j < n ; j ++)
                cout<<v[i][j]<<" ";      //改为matrix[i][j] = v[i][j]; 也可通过
            cout<<endl;
        }
    }
};

但是已规定原地和变换，且原函数无返回值，即输入矩阵matrix默认为评测对象，若修改其他矩阵返回的仍是原输入矩阵。

代码：先沿着副对角线翻转一次，再沿着水平中线翻转一次。时间复杂度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 = 0; j < n - i; j ++)
                swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);
        }
        //沿着水平中线翻转
        for (int i = 0; i < n/2; i ++)
            for (int j = 0; j < n; j ++)
                swap(matrix[i][j], matrix[n - 1 - i][j]);
    }
};