欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode初级算法之数组:旋转图像

程序员文章站 2022-04-28 10:05:09
...

题目描述:
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 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]
]

思路一: 矩阵转置+镜像翻转

这个题拿过来的第一个思路,就是矩阵转置和镜像水平翻转, 类似下面的图像,拿样例中的第二个举例:
LeetCode初级算法之数组:旋转图像
所以这个题比较容易理解的方式就是转置和水平镜像翻转了,实现起来也比较简单, 遍历一遍二维数组,先进行转置,然后遍历一遍行,每一行逆序即可,代码如下:

class Solution {
public:
    void rotate(vector<vector<int> >& matrix) {
        int rownum = matrix.size();
        int colnum = matrix[0].size();

        // 将矩阵转置
        for (int i=0; i<rownum; i++)
        {
            for (int j=0; j<i; j++)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 每一行对称翻转
        for (int i=0; i<rownum; i++)
        {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

时间复杂度: O(n^2) 空间复杂度O(1) 没有额外的空间开销

思路二: 直接翻转

上面的思路使用了两次矩阵翻转,其实只需要遍历一遍矩阵,进行一次翻转就可以, 我们看看应该怎么翻转:
LeetCode初级算法之数组:旋转图像
所以这个思路的关键就是遍历的时候取好终止条件,和交换的时候,下标的对应位置。 这个其实还是有点麻烦的

  • 对于matrix1来说,我们遍历的下标,行的范围是第0行-第1行,列的范围是第0列即可, 即元素1和4打头。 如下图:
    LeetCode初级算法之数组:旋转图像
    *对于matrix2来说,我们遍历的下标,行的范围第0行和第1行,列的范围下标是第0列和第1列。 如下图:
    LeetCode初级算法之数组:旋转图像
    交换的时候,下标的对应位置如上图所示,这个理解的时候,可以在原矩阵标出ij的位置,然后找到转置的ji的位置,然后在看交换是下标的对应位置。

所以一次遍历即可实现,最终的代码如下:

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++)     // 列的遍历范围
            {
             // 由于是旋转赋值,所以temp记录的是最后一个位置上的元素
             //然后逆时针进行覆盖,见上面的图。
                int temp = 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] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }
    }
};

这个的效率要比第一个思路的效率高一些,时间复杂度和空间复杂度和上面的那个一样。 但是只用一次遍历即可。
这个的关键就是行列遍历的终止条件和元素交换的下标对应。

小总:

这个题的第二种思路虽然效率高一些,但是比较难想到,并且如果对应不好终止条件,有可能转多了,下标也比较难对应,所以有的时候,第二种思路作为一种小拓展,第一种思路比较好理解一些。 这是旋转90度,如果逆时针旋转90或者是多少度的时候,也最好先从第一个思路开始出发,看看能不能简单的转置加逆序搞定,搞不定的时候,再考虑第二种思路。