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)，我们仅使用常数空间进行交换操作。所有操作都是原地进行的。