Day28 旋转图像

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

https://leetcode-cn.com/problems/rotate-image/

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像

示例1：

image

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例2：

image

输入：matrix = [[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]]

示例3：

输入：matrix = [[1]]
输出：[[1]]

示例4：

输入：matrix = [[1,2],[3,4]]
输出：[[3,1],[4,2]]

提示：

matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Java解法

思路：

• 比较可以得知 横向的数组转换为竖向的数组

• 不用第二个矩阵意味着转换时的中间数据需要被记录下来，所以需要在当前矩阵操作，尝试记录变化关系时可得知第一个顶点的变化关系如下，从而推导出后续，同时遍历的圈数由外向内，所以是length-2

  int temp = matrix[0][0];
  matrix[0][0] = matrix[length - 1][0];
  matrix[length - 1][0] = matrix[length - 1][length - 1];
  matrix[length - 1][length - 1] = matrix[0][length - 1];
  matrix[0][length - 1] = temp;
  

  image image

package sj.shimmer.algorithm.ten_3;

import sj.shimmer.algorithm.Utils;

/**
 * Created by SJ on 2021/2/21.
 */

class D28 {
    public static void main(String[] args) {
        int[][] matrix = {
//                new int[]{1, 2, 3},
//                new int[]{4, 5, 6},
//                new int[]{7, 8, 9},
//                new int[]{1, 2, 3, 4},
//                new int[]{5, 6, 7, 8},
//                new int[]{9, 10, 11, 12},
//                new int[]{13, 14, 15, 16},
//                new int[]{1, 2, 3, 4, 5},
//                new int[]{6, 7, 8, 9, 10},
//                new int[]{11, 12, 13, 14, 15},
//                new int[]{16, 17, 18, 19, 20},
//                new int[]{21, 22, 23, 24, 25},
                new int[]{2, 29, 20, 26, 16, 28},
                new int[]{12, 27, 9, 25, 13, 21},
                new int[]{32, 33, 32, 2, 28, 14},
                new int[]{13, 14, 32, 27, 22, 26},
                new int[]{33, 1, 20, 7, 21, 7},
                new int[]{4, 24, 1, 6, 32, 34},
        };
        rotate(matrix);
        for (int[] ints : matrix) {
            Utils.logArray(ints);
        }
    }

    public static void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 1) {
            return;
        }
        int length = matrix.length;
        for (int k = 0; k < length / 2 + 1; k++) {        //需要遍历的圈数 length/2
            for (int i = k; i < length - 1 - k; i++) {
                int temp = matrix[k][i];
                matrix[k][i] = matrix[length - 1 - i][k];
                matrix[length - 1 - i][k] = matrix[length - 1 - k][length - 1 - i];
                matrix[length - 1 - k][length - 1 - i] = matrix[i][length - 1 - k];
                matrix[i][length - 1 - k] = temp;
            }
        }
    }
}

image

官方解

https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/

1. 使用辅助数组

   开始是这么设想的但由于后续数组遍历时有多个数据，相当于用了一个新的矩阵所以没有继续做下去

   public void rotate(int[][] matrix) {
       int n = matrix.length;
       int[][] matrix_new = new int[n][n];
       for (int i = 0; i < n; ++i) {
           for (int j = 0; j < n; ++j) {
               matrix_new[j][n - i - 1] = matrix[i][j];
           }
       }
       for (int i = 0; i < n; ++i) {
           for (int j = 0; j < n; ++j) {
               matrix[i][j] = matrix_new[i][j];
           }
       }
   }
   

   • 时间复杂度：O(N^2)
   • 空间复杂度：O(N^2)

2. 原地旋转

   主要思路一致，代码也大致相同，就是自己空间想象能力太差，坐标转换太坑自己了

   public void rotate(int[][] matrix) {
       int n = matrix.length;
       for (int i = 0; i < n / 2; ++i) {
           for (int j = 0; j < (n + 1) / 2; ++j) {
               int temp = matrix[i][j];
               matrix[i][j] = matrix[n - j - 1][i];
               matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
               matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
               matrix[j][n - i - 1] = temp;
           }
       }
   }
   

   • 时间复杂度：O(N^2)
   • 空间复杂度：O(1)

3. 用翻转代替旋转

   水平翻转--对角线翻转：节省了不少思考

   public void rotate(int[][] matrix) {
       int n = matrix.length;
       // 水平翻转
       for (int i = 0; i < n / 2; ++i) {
           for (int j = 0; j < n; ++j) {
               int temp = matrix[i][j];
               matrix[i][j] = matrix[n - i - 1][j];
               matrix[n - i - 1][j] = temp;
           }
       }
       // 主对角线翻转
       for (int i = 0; i < n; ++i) {
           for (int j = 0; j < i; ++j) {
               int temp = matrix[i][j];
               matrix[i][j] = matrix[j][i];
               matrix[j][i] = temp;
           }
       }
   }
   

   • 时间复杂度：O(N^2)
   • 空间复杂度：O(1)