描述

给定一个 nxn的二维数组表示一个图像的数据，写一个函数把图像顺时针旋转90度。

可以在原地进行旋转吗？

分析

首先沿着副对角线翻转一次，然后沿着水平中线翻转一次，如下图所示：

示意图

或者也可以首先沿着水平线翻转一次，再沿着主对角线翻转也可以。

实现

// Rotate Image
void rotateImage(vector<vector<int>>& A)
{
    const int n = A.size();
    
    // 沿着副对角线翻转
    for (int i=0; i<n; i++) {
        for (int j=0; j<n-i; j++) {
            swap(A[i][j], A[n-1-j][n-1-i]);
        }
    }
    
    // 沿着中线翻转
    for (int i=0; i<n/2; i++) {
        for (int j=0; j<n; j++) {
            swap(A[i][j], A[n-1-i][j]);
        }
    }
}

可以看出时间复杂度为O()，空间复杂度为O(1)。