旋转矩阵--原地修改

0x01.问题

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

挑战：不占用额外内存空间能否做到？

输入示例：
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

输出示例：
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

来自程序员面试经典

Java函数形式：    public void rotate(int[][] matrix)

0x02.要点分析

首先，读懂旋转矩阵的具体含义：

• 以四个字节为一组，向右旋转90度。

这样说肯定比较抽象，不妨来看一下图：

图片来源于Leetcode

我们观察一下旋转后每一个元素变动的位置。

• 我们可以发现对每一个元素旋转，影响到了4个元素，所以，如果我们不适用额外的数组，那么我们就一定要在一次旋转操作中同时改变4个元素，这样就不需要使用额外的数组。

经过分析得到，这个四个元素相对于第一个修改的元素的位置是：

• a[i][j]–>a[n-j-1][i]–>a[n-i-1][n-j-1]–>a[j][n-i-1]。

所以我们只需要轮换这4个元素就行了。

而且我们发现，只需要修改上半部分，就可以旋转完成，内层只需要到n-i-2就行了，所以我们可以得到循环的边界条件：

• 外层i<n/2，内层j<n-i-1。

经过对位置元素的分析，我们还可以发现，如果将这个矩阵先上下翻转，再沿对角线翻转，也是可以达到同样效果的。

0x03.解决代码–上下，对角线翻转

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

0x04.解决代码–四数轮换

class Solution {
    public void rotate(int[][] matrix) {
        int n=matrix.length;
        for(int i=0;i<n/2;i++){
            for(int j=i;j<n-i-1;j++){
                int temp=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]=temp;
            }
        }
        return;
    }
}

Leetcode-4.7每日一题打卡完毕！

心情日记：希望你所珍惜的，正是你所期待的！

ATFWUS --Writing By 2020–04-07