红色php企业网站模板下载,合肥市城乡建设局2019网站,电商seo是什么,怎样找网站LeetCode 48.旋转图像
题目描述
给定一个 n x n 的二维矩阵 matrix#xff0c;表示一个图像。请你将该图像顺时针旋转 90 度。
说明#xff1a;
你必须在 原地 修改输入的二维矩阵。你可以假设矩阵的所有元素将会是整数。
示例 1:
输入:
[[1, 2, 3],[4, 5, 6],[7, 8, …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 度可以通过两步操作来实现 矩阵转置首先对矩阵进行转置操作即将矩阵的行和列交换。转置后的矩阵是将原矩阵的第 i 行变成第 i 列。 举个例子 原矩阵 [1, 2, 3] [4, 5, 6] [7, 8, 9] 转置后的矩阵 [1, 4, 7] [2, 5, 8] [3, 6, 9] 水平翻转然后对转置后的矩阵进行水平翻转即将每一行的元素顺序反转。这可以通过交换每一行的元素两端进行实现。 水平翻转后的矩阵 [7, 4, 1] [8, 5, 2] [9, 6, 3] 通过这两步操作即可完成矩阵的 90 度顺时针旋转。 复杂度分析 时间复杂度O(n^2)其中 n 是矩阵的行数或列数。我们需要遍历矩阵的所有元素两次一次用于转置操作另一次用于水平翻转操作。 空间复杂度O(1)我们仅使用常数空间进行交换操作。所有操作都是原地进行的。
