面试刷题：旋转矩阵 Q0048

By 青衣极客 Blue Geek In 2020-04-13

旋转一个矩阵在数学上来说确实不算是一件困难的事情，但是在编程实现上，如果要求 原处修改，那确实就有了一些难度。这种难度并不是技巧上的，而是逻辑上的。这种将数据在内存上倒腾来倒腾去是一个很重要的编程训练，因为这就是程序员的绝大多数工作内容。这里就通过Leetcode Q0048 旋转矩阵来聊一聊这个话题。

1. 题目 Leetcode Q0048 旋转矩阵

给定一个 $n \times n$ 的二维矩阵表示一个图像，将图像顺时针旋转 $90$ 度。 说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例1

示例2

2. 解决思路

对于这种需要“原处修改”的旋转问题，我们可以使用“削皮”的思路，即每次调整一圈元素，逐圈调整。假设该圈所在的行中有 $n$ 个元素，那么只需对前 $n-1$ 个元素进行调整，每次调整四个边，那也就是说需要对一圈元素需要移动 $4*(n-1)$ 次？ 不对，应该是 $5*(n-1)$ 次，因为我们必须将第一个被覆盖的元素备份，这样才能最终将第一个元素的数值移动到最后一个元素上。具体的流程如下图所示：

从图中可以看出，每一次轮换都需要5步操作才能将 $4$ 个边上对应位置的元素旋转过来。当然如果遇到 $n=1$ 的圈，那就不用再轮换了。可以计算出，这种思路的时间复杂度为 $O(n^2)$。

3. 解决方案

除了理清以上轮换的逻辑，还有一个难点，那就是精确取到想要的每个元素。这一点实在没办法使用图来表示，那就直接看C++的解决方案吧。

class Solution {
public:
    // 执行用时 :4 ms, 在所有 C++ 提交中击败了84.58% 
    // 内存消耗 :9.2 MB, 在所有 C++ 提交中击败了5.22%
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = n / 2, size = n, tmp=0;
        for (int i=0; i<m; ++i) {
            for (int j=0; j<size-1; ++j) {
                // backup r = 0, c = j
                tmp = matrix[i][i + j];
                // r = size - 1 - j, c = 0;
                matrix[i][i+j] = matrix[i + size-1-j][i];
                // r = size - 1, c = size - 1 - j
                matrix[i + size-1-j][i] = matrix[i + size - 1][i + size - 1 -j];
                // r = j, c = size - 1
                matrix[i + size - 1][i + size - 1 -j] = matrix[i + j][i + size - 1];
                // r = 0, c = j;
                matrix[i + j][i + size - 1] = tmp;
            }
            size -= 2;
        }
    }
};

解决方案的核心就是循环内的5条赋值语句，而其中每个元素的索引是值得仔细考虑的，这涉及到C++数组的子数组索引方式，子数组的索引必须依赖大数组的列数。

• Previous
  复盘Github中间人攻击事件疑云
• Next
  面试刷题：钟针之间的角度 Q1344