LeetCode初级算法——旋转图像

题目:给定一个 × 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]
]

初看这个题目的时候,哦,就是个数组元素移动问题嘛,于是开始在草稿纸上涂涂写写,找规律,写出程序,运行。。。咦!结果错误!行吧,看来还是我脑子不好使,那能怎么办,百度呗。。。

代码如下:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix[0].length;
        for(int i = 0; i < n/2; i++){
            for(int j = i; j < n - 1 - i; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = tmp;
            }
        }
    }
}

 

看起来是不是想打人?这么多i、j、n的,这么多符号,到底啥意思?那就分析一下~

首先,由于是顺时针旋转九十度,且是矩阵,那么可以每次变换正方形的四个顶点,以下图为例:

先是1、3、9、7变换位置,然后2、6、4、8变换位置,由于中心只有5一个元素,所以保持不变。

再以下图为例:

先是5、11、1、15变换位置,

再是1、10、12、13变换位置,

然后9、7、14、2变换位置,

最后4、8、6、3变换位置。

看到这里差不多就可以发现规律了,需要两层循环,外层循环控制行,内层循环控制列。每次循环变换四个顶点,内层循环变换完该正方形的所有顶点,外层循环再到一层层深入正方形中心。

class Solution {
    public void rotate(int[][] matrix) {
        //获取数组长度
        int n = matrix[0].length;
        //i为行,由于正方形是对称的,所以只需要循环n/2次
        for(int i = 0; i < n/2; i++){
            //每次循环不仅行在变化,列也在变化,所以列从i开始
            for(int j = i; j < n - 1 - i; j++){
                //保存左上角的值
                int tmp = matrix[i][j];
                //将左上角的值变换成左下角的值
                //内层循环中:左上角的元素行不变,列递增,左下角的元素行递减,列不变
                matrix[i][j] = matrix[n - j - 1][i];
                //将左下角的值变换成右下角的值
                //内层循环中:左下角的元素行递减,列不变,右下角的元素行不变,列递减
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                //将右下角的值变换成右上角的值
                //内层循环中:右下角的元素行不变,列递减,右上角的元素行递增,列不变
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                //将右上角的值变换成左上角的值
                //内层循环中:右上角的元素行递增,列不变,左上角的元素行不变,列递增
                matrix[j][n - i - 1] = tmp;
            }
        }
    }
}

 

文章已创建 65

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部