Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

首先我想到的是从中心往四周开始每一圈旋转,那么就用一个r来表示到中心的距离,但是如果通过r来确定每个旋转矩阵的长度,n是奇数/偶数的情况不一样,分别计算起来很麻烦。
所以我们还是通过每个小矩阵(框)最左上角到0,0的距离来计算旋转矩阵,这样代码会更加简洁:

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int d = 0; d < n/2; d++)
        {
            for (int i = d; i < n - 1 - d ; i++)//d代表正在旋转的矩阵框到0,0的距离,那么i就是当前正在旋转的元素到矩阵框开头的距离,n-1-d是矩阵框尾。
            {
                swap4(  matrix, 
                        d,  i,
                        i,  n - 1 - d, 
                        n - 1 - d, n - 1 - i,
                        n - 1 - i, d
                        );
            }
        }
    }
    public void swap4 (int[][] matrix, int r1, int c1, int r2, int c2, int r3, int c3, int r4, int c4)
    {
        int temp = matrix[r1][c1];
        matrix[r1][c1] = matrix[r4][c4];
        matrix[r4][c4] = matrix[r3][c3];
        matrix[r3][c3] = matrix[r2][c2];
        matrix[r2][c2] = temp;
    }
}

另一种思路更加简洁,首先将矩阵转置(这个比较简单)然后再将每一行reverse,就得到了旋转90的图形。

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        //transpose the matrix 
        for (int r = 0; r < matrix.length; r++) {
            for (int c = r + 1; c < matrix[0].length; c++) {
                swap(matrix, r, c, c, r);
            }
        }
        //reverse every row
        for (int r = 0; r < matrix.length; r++) {
            int start = 0;
            int end = matrix[0].length - 1;
            while(start < end) {
                swap(matrix, r, start, r, end);
                start++;
                end--;
            }
        }
    }
    
    private void swap(int [][] matrix, int r1, int c1, int r2, int c2) {
        if (r1 == r2 && c1 == c2)
            return ;
        int tmp = matrix[r1][c1];
        matrix[r1][c1] = matrix[r2][c2];
        matrix[r2][c2] = tmp;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s