题解 | 顺时针旋转矩阵

class Solution {
  public:
    vector<vector<int>> rotateMatrix(vector<vector<int>>& mat, int n) {
        vector<vector<int>> result(n, vector<int>(n));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 顺时针旋转90度：mat[i][j] -> result[j][n-1-i]
                result[j][n - 1 - i] = mat[i][j];
            }
        }

        return result;
    }
};

class Solution {
public:
    vector<vector<int>> rotateMatrix(vector<vector<int>>& mat, int n) {
        // 分层旋转，从外层到内层
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            
            for (int i = first; i < last; i++) {
                int offset = i - first;
                
                // 保存上边
                int temp = mat[first][i];
                
                // 左边 -> 上边
                mat[first][i] = mat[last - offset][first];
                
                // 下边 -> 左边
                mat[last - offset][first] = mat[last][last - offset];
                
                // 右边 -> 下边
                mat[last][last - offset] = mat[i][last];
                
                // 上边 -> 右边
                mat[i][last] = temp;
            }
        }
        
        return mat;
    }
};

class Solution {
public:
    vector<vector<int>> rotateMatrix(vector<vector<int>>& mat, int n) {
        // 第一步：转置矩阵（沿主对角线翻转）
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(mat[i][j], mat[j][i]);
            }
        }
        
        // 第二步：水平翻转每一行
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                swap(mat[i][j], mat[i][n - 1 - j]);
            }
        }
        
        return mat;
    }
};

算法分析

方法一（使用额外空间）：

• 时间复杂度：O(N²)，需要遍历所有元素
• 空间复杂度：O(N²)，需要额外的N×N矩阵

方法二（分层旋转）：

• 时间复杂度：O(N²)
• 空间复杂度：O(1)，只使用常数个临时变量

方法三（转置+翻转）：

• 时间复杂度：O(N²)
• 空间复杂度：O(1)