题解 | #顺时针旋转矩阵#

我们可以用 两步翻转法 来实现矩阵顺时针旋转 90 度，而不使用额外的存储空间，从而满足空间复杂度 (O(1)) 的要求。具体操作如下：

思路

1. 矩阵转置：将矩阵的行列互换，即将元素 matrix[i][j] 转换为 matrix[j][i]。
2. 水平翻转：对每一行的元素从左到右互换，即将 matrix[i][j] 与 matrix[i][N-j-1] 交换。

通过这两步操作，矩阵会顺时针旋转 90 度。

算法步骤

假设矩阵为 (N \times N)：

1. 转置矩阵：遍历矩阵的上三角区，将 matrix[i][j] 与 matrix[j][i] 交换。
2. 水平翻转每一行：对每一行从左到右的元素进行交换，将 matrix[i][j] 与 matrix[i][N - j - 1] 交换。

代码实现

public class Solution {
    public int[][] rotateMatrix(int[][] matrix, int n) {
        // 1. 转置矩阵
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // 2. 水平翻转每一行
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
        
        return matrix;
    }
}

示例运行

输入：

int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

步骤：

步骤：

1. 转置：
2. 水平翻转：

输出：[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

复杂度分析

• 时间复杂度：(O(N^2))，因为需要遍历矩阵的每一个元素。
• 空间复杂度：(O(1))，因为操作在原矩阵上进行，不需要额外空间。