LeetCode.程序员面试金典.0107.Rotate Matrix 旋转矩阵

题目描述

《程序员面试金典（第 6 版）》面试题 01.07. 旋转矩阵
https://leetcode-cn.com/problems/rotate-matrix-lcci/

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

不占用额外内存空间能否做到？
 
示例 1:

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

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

示例 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]
]

---

解题过程

分层模拟旋转操作

从最外圈（层）开始，依次把每圈顺时针旋转90度。

旋转每一圈时，先把左上角的值保存为temp，留出位置给 左下角，然后依次
左下角 移到 左上角
右下角 移到 左下角
右上角 移到 右下角
左上角（temp） 移到 右上角
重复 n 次，n 是当前圈的边长-1

旋转示意图

时间复杂度 O(n^2)，空间复杂度 O(1)

private static class SolutionV2020 {
    public void rotate(int[][] matrix) {
        if (null == matrix || matrix.length < 2) {
            return;
        }
        // 层数（圈数）
        int levelCount = matrix.length / 2;
        // 从最外圈（层）开始，依次把每圈顺时针旋转90度
        for (int i = 0; i< levelCount; i++) {
            rotateCircle(matrix, i, i, matrix.length - 1 -i, matrix.length - 1 - i);
        }
    }

    // 把正方形 (x1,y1) (x2,y2) 上的元素做顺时针 90 度旋转
    private void rotateCircle(int[][] matrix, int x1, int y1, int x2, int y2) {
        // 需要旋转的元素个数
        int rotateTimes = x2 - x1;
        for (int k = 0; k < rotateTimes; k++) {
            // 暂存 左上角 元素，留出位置给 左下角
            int temp = matrix[x1][y1+k];
            // 左下角 移到 左上角
            matrix[x1][y1+k] = matrix[x2-k][y1];
            // 右下角 移到 左下角
            matrix[x2-k][y1] = matrix[x2][y2-k];
            // 右上角 移到 右下角
            matrix[x2][y2-k] = matrix[x1+k][y2];
            // 左上角 移到 右上角
            matrix[x1+k][y2] = temp;
        }
    }
}

水平翻转+主对角线翻转

先水平翻转：

5  1  9 11                 15 14 12 16
2  4  8 10                 13  3  6  7
------------   =水平翻转=>   ------------
13  3  6  7                  2  4  8 10
15 14 12 16                  5  1  9 11

再根据主对角线 \ 翻转：

15 14 12 16                   15 13  2  5
13  3  6  7   =主对角线翻转=>   14  3  4  1
 2  4  8 10                   12  6  8  9
 5  1  9 11                   16  7 10 11

主对角线翻转+左右翻转

再根据主对角线 \ 翻转：

1 2 3                   1 4 7
4 5 6   -> 主对角线翻转   2 5 8
7 8 9                   3 6 9

再 左右翻转

1 4 7                   7 4 1
2 5 8   -> 左右翻转      8 5 2
3 6 9                   9 6 3

---

GitHub代码

algorithms/leetcode/crack/_0107_RotateMatrix.java
https://github.com/masikkk/algorithms/blob/master/leetcode/crack/_0107_RotateMatrix.java

---