48. 旋转图像 (opens new window)

1.外圈旋转

解题思路：观察每次旋转后每个正方形的外层数组，可以发现上边旋转到了右边，右边旋转到了下边...因此每次遍历进行旋转变换时，仅旋转最外圈的元素。然后递归缩小圈的范围处理内圈。

开辟一个缓存数组空间，缓存每次要写入那条边的元素。

class Solution {
    public void rotate(int[][] matrix) {
        round(matrix,0,0,matrix.length-1);
    }
    public void round(int[][] matrix,int x,int a,int b){
        int limit=matrix.length/2;
        if(x>=limit) return;
        int step=0;
        int[] nums=new int[b-a+1];
        int n1=matrix[x][a],n2=matrix[x][b],n3=matrix[x+b-a][b],n4=matrix[x+b-a][a];
        while(step<4){
            for(int i=0;i<=b-a;i++){
                if(step==0){
                    nums[b-a-i]=matrix[x+b-a-i][b];
                    matrix[x+b-a-i][b]=matrix[x][b-i];
                }
                if(step==1){
                    int temp=matrix[x+b-a][a+i];
                    matrix[x+b-a][a+i]=nums[b-a-i];
                    nums[b-a-i]=temp;
                }
                if(step==2){
                    int temp=matrix[x+i][a];
                    matrix[x+i][a]=nums[b-a-i];
                    nums[b-a-i]=temp;
                }
                if(step==3){
                    matrix[x][b-i]=nums[b-a-i];
                }
            }
            step++;
        }
        matrix[x][a]=n4;
        matrix[x][b]=n1;
        matrix[x+b-a][b]=n2;
        matrix[x+b-a][a]=n3;
        round(matrix,x+1,a+1,b-1); 
    }
}

2.优化

解题思路：交换内外层遍历顺序，每次循环交换四条边上对应点的位置。使用一个变量保存四个数交换时的中间状态，不需要开辟一个边大小的数组。

class Solution {
    public void rotate(int[][] matrix) {
        round(matrix,0,0,matrix.length-1);
    }
    public void round(int[][] matrix,int x,int a,int b){
        int limit=matrix.length/2;
        if(x>=limit) return;
        for(int i=0;i<=b-a-1;i++){
            //右
            int temp=matrix[x+i][b];
            matrix[x+i][b]=matrix[x][a+i];
            //下
            int swp=matrix[x+b-a][b-i];
            matrix[x+b-a][b-i]=temp;
            temp=swp;
            //左
            swp=matrix[x+b-a-i][a];
            matrix[x+b-a-i][a]=temp;
            temp=swp;
            //上
            matrix[x][a+i]=temp;
        }
        round(matrix,x+1,a+1,b-1); 
    }
}