算法题——旋转图像（旋转矩阵）

浅浅的花香味﹌ 2024-03-23 22:18 104阅读 0赞

###### 声明 ######

该系列文章仅仅展示个人的解题思路和分析过程，并非一定是优质题解，重要的是通过分析和解决问题能让我们逐渐熟练和成长，从新手到大佬离不开一个磨练的过程，加油！

###### 原题链接 ######

[旋转图像备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。![icon-default.png_t_N6B9][]https://leetcode.cn/problems/rotate-image/][IT _ Dream Offer_icon-default.png_t_N6B9_https_leetcode.cn_problems_rotate-image]

###### 算法分析 ######

若矩阵的行列数为N，设i表示行索引，i属于\[1,N\]，按照题意旋转矩阵则可以理解为我们需要将第i行的所有元素转换为第N-i+1列，如示例1所示，第1行为\[1,2,3\]，旋转后的第1行则变成了第3列，第2行与第3行同样如此。

![3d9e44169bee4a7cb0fa54bb66fa024c.png][] 图（1）

![deae1e47699843bcb4970599d6186e25.png][] 图（2）

PS:经现有测试该方法适用于行列数相同的矩阵，但不确定是否适用于行列数不同的矩阵。

**如图（1）索引分别为(0,0)，(0,1)，(0,2)，(0,3)，(1,3)，(2,3)，(3,3)，(3,2)，(3,1)，(3,0)，(2,0)，(1,0)的点围成了一个圈，假设我们称之为矩阵圈。**那么由外向内我们依次称为第1层矩阵圈，第2层矩阵圈，……第n层矩阵圈。图（1）所示有两个矩阵圈，第1层矩阵圈的索引集合为\[(0,0)，(0,1)，(0,2)，(0,3)，(1,3)，(2,3)，(3,3)，(3,2)，(3,1)，(3,0)，(2,0)，(1,0)\]，第2层矩阵圈的索引集合为\[(1,1)，(1,2)，(2,2)，(2,1)\]。

如图（1）和图（2）我们可以发现通过对每个矩阵圈的旋转即可完成对整个矩阵的旋转，而对矩阵圈的旋转实际上就是对矩阵圈进行点交换。**点交换的意思是交换矩阵圈四个边上的点，并且每个点是相互对应的。**

如图（3）所示，第一次交换索引为(0,0)和索引为(0,3)的点，第二次交换索引为(0,0)和索引为(3,3)的点，第三次交换索引为(0,0)和索引为(3,0)的点，我们把这称为矩阵圈的点交换。而这仅仅是矩阵圈的第一次点交换，假设该矩阵圈的行数和列数均为m，那么旋转该矩阵圈则需要(m-1)次点交换。

![4ae5acdc4f45495da238bac174790c67.png][] 图（3）

![5e4064d89e01424e9f55aba5e5154f59.png][] 图（4）

![0679dc33233547dcb81c7c97b0f8543d.png][] 图（5）

![cf0d588f23b745ef924d3069a022c8eb.png][] 图（6）

图（3）（4）（5）（6）则为该矩阵圈的一次完整的90°旋转。

为了从定量角度分析这个规律。首先我们可以定义四个变量rowA,rowB,colA,colB分别表示每一个矩阵圈的首行尾行以及首列尾列，并对它们进行初始化，rowA=0,rowB=m-1,colA=0,colB=m-1，rowA指向当前矩阵圈第一行，rowB指向最后一行，colA指向当前矩阵圈第一列，colB指向最后一列。其次我们再定义一个变量count，表示当前矩阵圈需要进行点交换的次数，count属于\[1,m-1\]。那么该矩阵圈进行点交换的四个点的索引分别为：

(rowA,colA+count-1), (rowA+count-1,colB),

(rowB,colB-count+1), (rowB-count+1,colA)

我们只需要按照(rowA+count-1,colB),(rowB,colB-count+1),(rowB-count+1,colA)的索引顺序分别与索引为(rowA,colA+count-1)的点进行交换即可，每完成一次点交换则count进行+1操作，当count等于m-1时表示该矩阵圈的90°旋转完成。所以接下来需要收缩rowA,rowB,colA,colB四个变量，从而指向下一层矩阵圈，收缩操作即对rowA和colA进行+1操作，对rowB和colB进行-1操作，重复上述过程从外向内旋转矩阵圈直至rowA、rowB、colA、colB四个变量的值相等则表明整个矩阵完成了90°的旋转。

###### 代码示例（C\#） ######

public void Rotate(int[][] matrix)
    {
        //定义变量
        int rowA = 0, rowB = matrix.Length - 1, colA = 0, colB = matrix[0].Length - 1, count = 1;
        //逻辑主体
        while (count <= colB - colA)
        {
            //矩阵点交换
            (matrix[rowA][colA + count - 1], matrix[rowA + count - 1][colB]) = (matrix[rowA + count - 1][colB], matrix[rowA][colA + count - 1]);
            (matrix[rowA][colA + count - 1], matrix[rowB][colB - count + 1]) = (matrix[rowB][colB - count + 1], matrix[rowA][colA + count - 1]);
            (matrix[rowA][colA + count - 1], matrix[rowB - count + 1][colA]) = (matrix[rowB - count + 1][colA], matrix[rowA][colA + count - 1]);
            //矩阵圈收缩
            if (count == colB - colA)
            {
                colA++;
                colB--;
                rowA++;
                rowB--;
                count = 1;
            }
            else count++;
        }
    }

###### 算法解说 ######

结合算法分析过程，我们将矩阵的旋转转换为矩阵圈的旋转，然后将矩阵圈的旋转转换为矩阵点的交换，也就是说矩阵旋转的本质就是矩阵中各个元素的交换，实际上我们从图（1）和图（2）就可以发现，转换前的矩阵的第一行变成了转换后的矩阵的最后一列，但是本文的解题思路并未采取这种方式。

由于每个矩阵圈都有四条边，所以旋转矩阵圈就是在交换四个边上指定的元素，具体的思路算法分析中已经描述得比较详尽，对于如何将分析过程转换为代码，对于多数算法题来说本质上都是明确两个重点，一个是变量，一个是逻辑主体。本题中所用到的变量包括用于明确当前矩阵圈的四个指针，还有一个用于记录当前矩阵圈进行点交换的次数。而逻辑主体则包括矩阵点交换和矩阵圈收缩，同时需要明确逻辑主体退出的条件。

[icon-default.png_t_N6B9]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/95791d163e00443f958ea5a08f41bf11.png
[IT _ Dream Offer_icon-default.png_t_N6B9_https_leetcode.cn_problems_rotate-image]: https://leetcode.cn/problems/rotate-image/
[3d9e44169bee4a7cb0fa54bb66fa024c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8ff7b5d55c6144849946c3182a6f4079.png
[deae1e47699843bcb4970599d6186e25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cfe94698db264423b4b237d008061ef9.png
[4ae5acdc4f45495da238bac174790c67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/27c633a5e99c48f79154563e45a10f85.png
[5e4064d89e01424e9f55aba5e5154f59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8e177bc39c7a4744b5d97de01bbc4f7f.png
[0679dc33233547dcb81c7c97b0f8543d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/19b1ad28ae524691b92fe803a5ac785d.png
[cf0d588f23b745ef924d3069a022c8eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1c0e7efa2c1c46f2bcd0b30149b0c4ad.png