LEETCODE 48. Rotate Image 解题思路分析

题目大意:

旋转图像

给定一个 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]
 ]

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=48

解题思路分析:

本题要求使用原地算法,即不能使用额外的数组进行变换。如果在当前二维数组内进行90度旋转操作的话,我们可以从最外圈向最内圈逐圈变换。对于任意一个点A做旋转时,我们需要知道它将要移动到的位置B,而B又要移动到其旋转后的位置C。看似麻烦的操作,其实是有规律的,看下图:

图中最外圈所有相同颜色的格子都存在4个,他们处于对称的位置上,按照顺时针移动每一个格子到下一个相同颜色位置后,图像就会完成90度旋转。在矩阵的每一圈中,他都存在4条边,注意,我们不能将第一个格子到最后一个格子区间看做一条边,这样的话,四条边会在四个顶角出现重合,正确的方式如下图所示:

对于当前边,我们只要事先取得每一点的数值,以及与该点相对称的另外3个点的数值,再将其顺时针交换即可。

实现代码:

public void rotate(int[][] matrix) {
    int length=matrix.length;
    // 循环每一圈
    for(int row=0;row<length/2;row++){
        // 循环当前圈的上边上的每一个点
        for(int col=row;col<length-row-1;col++){
            // 取得当前点以及与之相对称的另外三个点坐标
            int tr=row, tc=col;
            int rr=tc, rc=length-1-tr;
            int br=rc, bc=length-1-rr;
            int lr=bc, lc=length-1-br;
            // 取得四个点的数值
            int top=matrix[tr][tc];
            int right=matrix[rr][rc];
            int bottom=matrix[br][bc];
            int left=matrix[lr][lc];
            // 将四个点的数值顺时针插入数组
            matrix[tr][tc]=left;
            matrix[rr][rc]=top;
            matrix[br][bc]=right;
            matrix[lr][lc]=bottom;
        }
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.

Memory Usage: 38.3 MB, less than 5.77% of Java online submissions for Rotate Image.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-48-rotate-image-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。