leetcode hot100【LeetCode 48.旋转图像】java实现

LeetCode 48.旋转图像

题目描述

给定一个 n x n 的二维矩阵 matrix，表示一个图像。请你将该图像顺时针旋转 90 度。

说明：

• 你必须在 原地 修改输入的二维矩阵。
• 你可以假设矩阵的所有元素将会是整数。

示例 1:

输入:

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

输出:

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

示例 2:

输入:

[
 [ 5, 1, 9, 11],
 [ 2, 4, 8, 10],
 [13, 3, 6, 7],
 [15, 14, 12, 16]
]

输出:

[
 [15, 13, 2, 5],
 [14, 3, 4, 1],
 [12, 6, 8, 9],
 [16, 7, 10, 11]
]

Java 实现代码

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // 1. 转置矩阵
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 交换matrix[i][j]和matrix[j][i]
                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++) {
                // 交换matrix[i][j]和matrix[i][n-j-1]
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}

解题思路

旋转矩阵的核心思想是将每个元素移到它旋转后的新位置。为了达到顺时针旋转 90 度，可以通过两步操作来实现：

1. 矩阵转置：首先对矩阵进行转置操作，即将矩阵的行和列交换。转置后的矩阵是将原矩阵的第 i 行变成第 i 列。
   举个例子： 原矩阵： [1, 2, 3] [4, 5, 6] [7, 8, 9] 转置后的矩阵： [1, 4, 7] [2, 5, 8] [3, 6, 9]

2. 水平翻转：然后对转置后的矩阵进行水平翻转，即将每一行的元素顺序反转。这可以通过交换每一行的元素两端进行实现。

       水平翻转后的矩阵：    [7, 4, 1]    [8, 5, 2]    [9, 6, 3]    ```
   
   

通过这两步操作，即可完成矩阵的 90 度顺时针旋转。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是矩阵的行数（或列数）。我们需要遍历矩阵的所有元素两次：一次用于转置操作，另一次用于水平翻转操作。

• 空间复杂度：O(1)，我们仅使用常数空间进行交换操作。所有操作都是原地进行的。