Rotate Image [LeetCode 100]

Frequency: ♥ ♥                Difficulty: ♥ ♥ ♥
Data Structure: Matrix
Algorithm:

Problem Description

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?

问题分析

这是道CC150上的原题，方法还挺多。

解法一

先来个最朴素的想法吧，创建一个矩阵，把旋转后的结果存入该矩阵中。

// wrong solution!!!
public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length==0)
            return ;
        int m = matrix.length;
        int[][] result = new int[m][m];
        // rotate
        for(int i=0; i<m; i++){
            for(int j=0; j<m; j++){
                result[j][m-1-i] = matrix[i][j];
            }
        } 
        matrix = result;
    }
}

上面的解法是不能通过LeetCode OJ（会被判定为错误答案）。这里是因为在Java中传入的matrix（object）是pass by reference，虽然return的矩阵是经过旋转后的结果，但是OJ检测的是原matrix有没有被rotated，所以不会通过。修改方法很简单，先复制原matrix到新建的矩阵中，然后再对复制的矩阵进行旋转，结果存入到原matrix中。

解法二

解法二就是根据旋转的本质进行的实现，由外而内，由前往后，有着O(1)的空间复杂度。

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i=0;i<n/2;++i) {
            int start = i;
            int end = n - i - 1;
            for(int j=0;j<(end-start);++j) {
                int topLeft = matrix[start][start+j];
                // bottom left => top left
                matrix[start][start+j] = matrix[end-j][start];
                // bottom right => bottom left
                matrix[end-j][start] = matrix[end][end-j];
                // top right => bottom right
                matrix[end][end-j] = matrix[start+j][end];
                // top left => top right
                matrix[start+j][end] = topLeft;
            }
        } 
    }
}

解法三

解法三首先沿逆对角线翻转一次，然后按x轴中线翻转一次（即先转置，然后再水平翻转）。

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix==null||matrix.length<=0) return;
        int n = matrix.length;
        // transpose
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                exch(matrix, i, j, j, i);
            }
        }
        // flip horizontal
        for(int i=0;i<n;i++) {
            for(int j=0;j<(n>>1);j++)
                exch(matrix, i, j, i, n-j-1);
        }
    }
    
    private void exch(int[][] matrix, int i, int j, int p, int q) {
        int temp = matrix[i][j];
        matrix[i][j] = matrix[p][q];
        matrix[p][q] = temp;
    }
}

 

 

查看更多LeetCode解题思路…