48. 旋转图像(中等)

Posted on In Views:

1，问题描述

48. 旋转图像

难度：中等

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

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

示例 1：

img

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

示例 2：

img

1
2
输入：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]]

提示：

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

2，初步思考

​ 模拟法：直接先找出数学规律

​ （i,j）——》（len-j-1,i）

​ （len-j-1,i）——》（len-i-1,len-j-1）

​ （len-i-1,len-j-1）——》（j,len-i-1）

​ （j,len-i-1）——》（len-i-1,j）

​ 翻转变换法：先水平翻转、再沿着左上对角线翻转！

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class _48旋转图像 {

    // 解法3:水平与竖直翻转
    public void rotate_flip(int[][] matrix) {
        int len = matrix.length;
        for (int i = 0; i < len / 2; ++i) {
            for (int j = 0; j < len; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len - i - 1][j];
                matrix[len - i - 1][j] = temp;
            }
        }

        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }


    // 解法2:原地旋转，利用
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        for (int i = 0; i < len / 2; i++) {
            for (int j = 0; j < (len + 1) / 2; j++) {// 只处理1/4区块
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len - 1 - j][i];// ok
                matrix[len - 1 - j][i] = matrix[len - 1 - i][len - 1 - j];
                matrix[len - 1 - i][len - 1 - j] = matrix[j][len - 1 - i];
                matrix[j][len - 1 - i] = temp;
            }
        }
    }

    // 解法1:使用辅助数组，暴力求解
    public void rotate_area(int[][] matrix) {
        int len = matrix.length;
        int[][] ans = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                ans[j][len - i - 1] = matrix[i][j];
            }
        }

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                matrix[i][j] = ans[i][j];
            }
        }
    }

    public static void main(String[] args) {
        _48旋转图像 rotate = new _48旋转图像();
        int[][] matrix = new int[][]{
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        rotate.rotate(matrix);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }


}