hot100 48.旋转图像

1.题目要求把一个方阵n * n的矩阵顺时针旋转90°。且要求不能创建另一个矩阵空间复杂度必须是O(1)。2.思路1顺时针旋转90°后位于ij的元素去哪了2竖着看——第一列的元素去到第一行。——第二列的元素去到第二行。——......——第j列的元素去到第j行。3横着看——第一行的元素去到最后一列。——第二行的元素去到倒数第二列。——......——第i行的元素去到第n - 1 - i列i从0开始。4所以位于第i行第j列的元素去到第j行第n - 1 - i列即ij-jn - 1 - i。5ij-jn - 1 - i可以通过两次翻转操作得到ij-转置ji-行翻转jn - 1 - i。——转置就是把矩阵按照主对角线翻转位于ij的元素去到ji。——行翻转就是把每一行都翻转位于ji的元素去到jn - 1 - i。6示例一的操作过程如下图所示7实现以下两步操作都可以原地实现。——转置把主对角线下面的元素matrix[i][j]和关于主对角线对称位置的元素matrix[j][i]交换。——行翻转遍历每一行row matrix[i]把左半边的元素row[j]和关于垂直中轴对称位置的元素row[n - 1 - j]交换。或者使用库函数翻转row。3.复杂度分析1时间复杂度O(n^2)其中n是matrix的行数和列数。2空间复杂度O(1)。附代码一写法一class Solution { public void rotate(int[][] matrix) { int n matrix.length; //第一步转置 for(int i 0;i n;i){ for(int j 0;j i;j){ //遍历对角线下方元素 int tmp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] tmp; } } //第二步行翻转 for(int i 0;i n;i){ //for(int[] row : matrix) for(int j 0;j n / 2;j){ //遍历左半元素 int tmp matrix[i][j]; //int tmp row[j]; matrix[i][j] matrix[i][n - 1 - j]; //row[j] row[n - 1 - j]; matrix[i][n - 1 - j] tmp; //row[n - 1 - j] tmp; } } } }二写法二可以把两个循环合并成一个循环。需要把遍历顺序调整为遍历对角线上方的元素这样每行遍历完之后这一行的元素后面就不会再被访问到可以直接做行翻转因为在转置过程中当处理到第i行时第0到第i - 1行已经完成了它们所有的转置交换并且已经翻转过了不会再被修改所以我们可以安全地修改第i行。class Solution { public void rotate(int[][] matrix) { int n matrix.length; for(int i 0;i n;i){ for(int j i 1;j n;j){ //遍历对角线上方的元素做转置 int tmp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] tmp; } for(int j 0;j n/2;j){ //遍历左半元素做行翻转 int tmp matrix[i][j]; matrix[i][j] matrix[i][n - 1 - j]; matrix[i][n - 1 - j] tmp; } } } }ACM模式import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取矩阵大小 int n scanner.nextInt(); // 读取矩阵元素 int[][] matrix new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { matrix[i][j] scanner.nextInt(); } } // 调用方法 Solution solution new Solution(); solution.rotate(matrix); // 输出结果 for (int i 0; i n; i) { for (int j 0; j n; j) { System.out.print(matrix[i][j]); if (j n - 1) { System.out.print( ); } } System.out.println(); } scanner.close(); } } class Solution { public void rotate(int[][] matrix) { int n matrix.length; // 第一步转置 for (int i 0; i n; i) { for (int j 0; j i; j) { // 遍历对角线下方元素 int tmp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] tmp; } } // 第二步行翻转水平镜像 for (int i 0; i n; i) { for (int j 0; j n / 2; j) { // 遍历左半元素 int tmp matrix[i][j]; matrix[i][j] matrix[i][n - 1 - j]; matrix[i][n - 1 - j] tmp; } } } }