分类处理实现高效地矩阵旋转，找规律

题目链接-来源：力扣（LeetCode）

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

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

示例 1：

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

思路：

我们可以将矩阵分组，方便我们进行旋转操作。我们发现每一次旋转操作，对于某一个位置的元素，只有与其相对应位置的另外 3 个元素是真正与其相关联的，我们可以一次性将这关联的四个位置「打包操作」（以示例 1 为例，不论我们旋转的角度是多少度，四个角落处永远都是被 1、3、7、9 四个数字占据，并且其相对位置不变，所以我们将其视为一个整体打包操作）。
这样我们只需遍历 1/4 规模的矩阵元素，以其作为起始元素，每一个起始元素与其相关联的另外 3 个元素划为一组同一操作。为了对齐考虑，方便我们按数字规律查找关联元素，我们可以这样查找起始元素：显然，我们只需查找 n / 2 行，因为剩余的行一定包含在我们查找的关联元素中；而在第 i 行中，我们只需访问其第 i 个到 第 n - 2 - i 个元素，因为剩余的列也一定包含在关联元素当中。按照这种查找方式，我们恰好能够找到 n * n / 4 个元素作为头部元素。
在每一轮操作中，设头部元素为 matrix[i][j]（注意这里的 i、j 满足前面所列的条件，否则之后的关联元素下标可能会越界），则与其相关联的另外 3 个元素分别为 matrix[n - 1 - j][i]、matrix[n - 1 - i][n - 1 -j]、matrix[j][n - 1 - i]，将这几个元素顺时针轮换一遍，即可得到符合条件的局部结果。

时间复杂度：O(n²)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 -j];
                matrix[n - 1 - i][n - 1 -j] = matrix[j][n - 1 -i];
                matrix[j][n - 1 -i] = tmp;
            }
        }
    }
}