给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定 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]
]

注意：本题与主站 48 题相同：https://leetcode-cn.com/problems/rotate-image/

思路1：暴力破解方法

占用额外内存空间

把第一列x个元素旋转90度之后，变成最后一行的x列元素

把第二列x个元素旋转90度之后，变成最后二行的x列元素

5 -> matrix[0][0] -> matrix[4][0]

1 ->matrix[0][1] -> matrix[4][1]

9 ->matrix[0][2] -> matrix[4][2]

11 ->matrix[0][3] -> matrix[4][3]

matrix[row][col] -> matrix[col][matrix.length-row-1] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * 暴力破解方法
 * [row][col] -> [col][length-row-1]
 * @param matrix
 */
public static void rotate(int[][] matrix) {
    // 新的数组
    int length = matrix.length;
    int[][] matrixNew = new int[length][length];

    for(int row=0; row< length; row++ ){
        for (int col = 0; col < length; col++) {
            matrixNew[col][length- row -1] = matrix[row][col];
        }
    }
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            matrix[i][j] = matrixNew[i][j];
        }
    }
}

思路2

先水平翻转,然后在对角线反转

matrix[row][col] -> matrix[n−row−1][col]

matrix[row][col] -> matrix[col][row]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void rotate2(int[][] matrix) {
    int length = matrix.length;
    // 先水平翻转
    for(int row=0; row< length / 2; row++ ){
        for (int col = 0; col < length; col++) {
            int temp = matrix[row][col];
            matrix[row][col] = matrix[length - row - 1][col];
            matrix[length - row - 1][col] = temp;
        }
    }
    // 对角线反转
    for(int row=0; row< length; row++ ){
        for (int col = 0; col < row; col++) {
            int temp = matrix[row][col];
            matrix[row][col] = matrix[col][row];
            matrix[col][row] = temp;
        }
    }
    
}

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/array-and-string/clpgd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。