心之所向便是光

Leetcode 48.旋转图像

  • 2021-06-09
  • 作者 Ender
  • 2.17K 字
  • 次阅读

题目描述：

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：matrix = [[1]]
输出：[[1]]

示例 4：

1
2
输入：matrix = [[1,2],[3,4]]
输出：[[3,1],[4,2]]

提示：

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

链接：

https://leetcode-cn.com/problems/rotate-image

题目分析

  题目要求我们使用原地算法，也即直接对矩阵进行操作。通过观察我们可以发现，顺时针旋转 90 度，也即每 4 个位置进行了依次更替。如下图所示。
leetcode48-1.png

  一共有多少组需要进行这样的更替呢？其实也就是矩阵的 1/4。下面以 4 × 4 和 5 × 5 的矩阵为例展示需要旋转的范围。我们只需要以左上角的色块为起点，对每一个位置进行对应位置的依次更替即可。需要注意依次更替的坐标对应关系，还有矩阵宽度为奇数时的划分方式（中心块无需更替）。
leetcode48-2.png
leetcode48-3.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < (n+1)/2; i++){
            for(int j = 0; j < n/2; j++){
                int temp = 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] = temp;
            }
        }
        return;
    }
};

  时间复杂度：$O(n^2)$，其中 $n$ 为矩阵的宽度。我们其实就是对矩阵的每个位置进行了相应的更替，需要操作的子矩阵大小为 $O(\lfloor{\frac{n+1}{2}}\rfloor\times\lfloor{\frac{n}{2}}\rfloor)=O(n^2)$，每次操作 5 步，为常数。
  空间复杂度：$O(1)$。原地算法，只用到了常数的额外空间。

官方题解

  官方题解中提到了另外一种巧妙的方法，也即利用翻转代替旋转。先将矩阵上下翻转，再按左上到右下的主对角线翻转，也可以得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-22