L48 旋转图像

题目链接

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

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 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]]

提示

• n == matrix.length == matrix[i].length
• $1 \le n \le 20$
• $-1000 \le \text{matrix}[i][j] \le 1000$

题解

这道题刚看上去很简单——直接新建一个同样大小的矩阵，然后映射过去就行了，但是题目不让~~，虽然我们这么写也能过，它又不知道 ᕦ ( ͡° ͜ʖ ͡°)ᕤ~~

那所谓的原地旋转可怎么办？直接修改的话，一个位置的新值可能会把原来的值覆盖掉，而这个原来的值后面可能还要继续使用，这样数据就丢了。

所以大致也就这两种办法了： 第一种就是借助临时变量，把即将被覆盖的数据先保存下来，再依次移动其他位置的数据。这里有一种很巧妙的"转轮法"，力扣题解区有一位大佬讲得很清楚，而且还带有动画演示，感兴趣的话可以直接移步学习：旋转图像——辅助矩阵与原地旋转。

第二种就是我们这篇使用的方法——找出规律，然后通过 swap 不断交换元素的位置。当然，swap 底层同样需要临时保存数据，不过这些细节我们不用管，我们直接用就行了。

接下来还是先观察图像，会发现：如果把原矩阵沿左上角到右下角的主对角线翻转一次（即转置一次），再把整个矩阵左右翻转一次，最终得到的结果刚好就是顺时针旋转 90° 后的矩阵。（这时你可能就好奇了，我是怎么发现的？其实我也没发现，我也是看了其他人的题解才知道哈哈，这个规律大概记一下就行，其他旋转题也是类似规律）

以示例 2 为例，就是下面这样：

知道规律后，代码就很简单了：

class Solution 
{
    public:
        void rotate(vector<vector<int>>& matrix) 
        {
            int n = matrix.size(); // 行数，本题中行数 = 列数

            //沿着左上到右下的对角线翻转：
            for(int i = 0;i < n;i++)
            {
                for(int j = 0;j < i;j++)
                    swap(matrix[i][j],matrix[j][i]);
            }

            //左右翻转，双指针
            for(int j_l = 0,j_r = n - 1;j_l < j_r ;j_l++,j_r--)
            {
                for(int i = 0;i < n;i++)
                    swap(matrix[i][j_l],matrix[i][j_r]);
            }
        }
};

首先通过 int n = matrix.size(); 得到行数，在本题中，也等于列数。这里顺便扩展一下，对于 vector<vector<int>> 构成的矩阵，如果行列数不相等，获取列数的方法是：matrix[i].size()，这里 i 一般取 0 就行。

接下来就开始转置，这里也不难，主要是注意循环条件控制，注意 j < i，也就是说只处理主对角线其中一侧的元素，不然全部遍历的话，换过去又换回来，不是白忙活了么~

左右翻转部分也很容易：这里使用两个指针，j_l 从最左边一列开始，j_r 从最右边一列开始，两边不断向中间靠近，直到指针相遇。内部就遍历当前两列中的每一行，把左边这一列和右边对应位置的元素全部交换即可。

这道题的代码特别简单，真正关键的其实就是前面观察出来的这个规律。

这道题我也借助 AI 补充了力扣提交代码之外的本地测试部分，可以直接在自己的编译器中输入数据并运行。完整代码已经整理到 GitHub：https://github.com/C571467648/blog。其他题目也是采用相同的方式整理，建议有需要的话一次性下载使用。如果觉得比较麻烦，或者只想研究题目本身，也可以直接在力扣平台研究 class Solution 部分的代码。

本题讲解就到这里啦，欢迎交流讨论~