如何购买虚拟主机做网站,百度软件下载,最新搜索引擎排名,福田祥菱v1质量怎么样旋转图像
给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1#xff1a; 输入#xff1a;matrix [[1,2,3],[4,5,6],[7,8,…旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1 输入matrix [[1,2,3],[4,5,6],[7,8,9]] 输出[[7,4,1],[8,5,2],[9,6,3]]
解题思路
1、首先我们将矩阵沿着主对角线左上到右下的对角线进行镜像翻转即将矩阵的行和列互换。2、然后再将每一行按照中心水平轴进行翻转即将每一行的元素顺序颠倒。
Java实现
public class RotateImage {public void rotate(int[][] matrix) {int n matrix.length;// Transpose the matrix 转换矩阵for (int i 0; i n; i) {//注意这里是ji,只能遍历左上角到右下角一半的矩阵for (int j i; j n; j) {int temp matrix[i][j];matrix[i][j] matrix[j][i];matrix[j][i] temp;}}// Reverse each row 反转每一行for (int i 0; i n; i) {int left 0, right n - 1;while (left right) {int temp matrix[i][left];matrix[i][left] matrix[i][right];matrix[i][right] temp;left;right--;}}}public static void main(String[] args) {RotateImage rotateImage new RotateImage();int[][] matrix {{1, 2, 3},{4, 5, 6},{7, 8, 9}};int[][] test {{ 1, 2, 3, 4},{ 5, 6, 7, 8},{ 9, 10, 11, 12},{13, 14, 15, 16}};System.out.println(Original Matrix:);printMatrix(matrix);rotateImage.rotate(matrix);System.out.println(Rotated Matrix:);printMatrix(matrix);System.out.println(Original Matrix:);printMatrix(test);rotateImage.rotate(test);System.out.println(Rotated Matrix:);printMatrix(test);}private static void printMatrix(int[][] matrix) {for (int[] row : matrix) {for (int num : row) {System.out.print(num );}System.out.println();}}
}
时间空间复杂度
时间复杂度O(n^2)其中 n 是矩阵的边长。空间复杂度O(1)只需要使用常数级别的额外空间
