分析

• 本题的考点：数组。

• 这一题的想法十分具有跳跃性，记住这种做法即可，核心想法是将旋转操作拆分成两个操作。

• 其实本质上这道题是计算机图形学的内容。另外线性代数也会研究这类问题。

• 让数组顺时针旋转：先上下翻转，再沿主对角线翻转;（也等价于先沿主对角线翻转，再左右翻转）。

• 让数组逆时针旋转：先左右翻转，再沿主对角线翻转;（也等价于先沿主对角线翻转，再上下翻转）。

代码

• C++

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {

        int n = matrix.size();
        // (1) 上下翻转
        for (int i = 0; i < n; i++)  // 翻转第i列
            for (int j = 0, k = n - 1; j < k; j++, k--)
                swap(matrix[j][i], matrix[k][i]);
        // (2) 沿主对角线翻转
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                swap(matrix[i][j], matrix[j][i]);
    }
};

• Java

class Solution {
    public void rotate(int[][] matrix) {

        int n = matrix.length;
        // (1) 上下翻转
        for (int i = 0; i < n; i++)  // 翻转第i列
            for (int j = 0, k = n - 1; j < k; j++, k--)
                swap(matrix, j, i, k, i);
        // (2) 沿主对角线翻转
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                swap(matrix, i, j, j, i);
    }

    private void swap(int[][] matrix, int x1, int y1, int x2, int y2) {
        int t = matrix[x1][y1]; 
        matrix[x1][y1] = matrix[x2][y2]; 
        matrix[x2][y2] = t;
    }
}

时空复杂度分析

• 时间复杂度：$O(n^2)$，n分别为输入数组的行数或列数。

• 空间复杂度：$O(1)$。