LeetCode 48. 旋转图像 规律题

题目描述

给定一个 \(n\*n\) 的二维矩阵，表示一张图片。
请将这张图片顺时针旋转 \(90^{\\circ}\)。

注意：

你只能进行原地操作，即：直接修改矩阵的值，且不可以分配一个新的二维数组。

样例1

输入：

[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

输出：

[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

样例2

输入：

[
  [ 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]
]

---

算法1

(操作分解) \(O(n^2)\)

分解成两个操作：

1. 先以左上-右下对角条线为轴做翻转；
2. 再以中心的竖线为轴做翻转；

时间复杂度：\(O(n^2)\)， 额外空间：\(O(1)\)

扩展：

顺时针 90： 主对角线（从左上到右下）翻转，然后从中间水平反转
逆时针 90： 主对角线翻转，然后从中间上下翻转
顺时针180和逆时针180 都是先主对角线翻转，然后副对角线翻转

C++ 代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i ++ )
            for (int j = i + 1; j < n; j ++ )
                swap(matrix[i][j], matrix[j][i]);
        for (int i = 0; i < n; i ++ )
            for (int j = 0, k = n - 1;
                    j < k; j ++, k -- )
                swap(matrix[i][j], matrix[i][k]);
    }
};

算法2

(一次遍历) \(O(n^2)\)

1. 将这个二维矩阵看成若干圈，每一圈都是进行一次 90 度旋转。每次旋转都是若干次 4 个数的轮换。
2. 所以我们从最外圈开始，首先更新 (0, 0), (0, n - 1), (n - 1, n - 1), (n - 1, 0) 这 4 个数，然后更新 (0, 1), (1, n - 1), (n - 1, n - 2), (n - 2, 0)，以此类推。
3. 然后往里走一圈，更新 (1, 1), (1, n - 2), (n - 2, n - 2), (n - 2, 1) 等等。
4. 每次的 4 个数下标轮换的规律也很好找。

时间复杂度

• 仅遍历数组一次，故时间复杂度为 \(O(n)\)。

空间复杂度

• 仅使用了常数个变量，故空间复杂度为 \(O(1)\)。

C++ 代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int s = 0; s < n/2; s++) {
            for (int i = s; i < n - 1 - s; i++) {
                int cx = s, cy = i, bak = matrix[cx][cy];
                for (int k = 0; k < 3; k++) {
                    int sx = n - 1 - cy, sy = cx;
                    matrix[cx][cy] = matrix[sx][sy];
                    cx = sx;
                    cy = sy;
                }
                matrix[cx][cy] = bak;
            }
        }
    }
};