LeetCode : Rotate Image #48

最近加入了一个邪恶的刷题组织，今天我要完成一道题的简单解析与算法实现分析，抽到了 Midum 的 Rotate Array。

Question

You are given an n x n 2 D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?

Analysis

这道题是一个多维数组变换的问题，题目要求一个 NxN 的二维的 Matrix，把这个 Matrix 顺时针翻转。

有两种实现方法，先讲最好理解的方法一。

解法一

先转置(transpose)，然后再左右对称地翻转(flip symmetrically)。示意图如下：

1
2
3
1 2 3     7 8 9     7 4 1
4 5 6  => 4 5 6  => 8 5 2
7 8 9     1 2 3     9 6 3

解法二

第二种方法就是直接按照题意翻转这个 matrix，只需要找到翻转的点与点之间的关系。

//解析正在分析中

Solution

解法一(Java)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public void rotate(int[][] matrix) {
        int N = matrix.length;
        if(N>1&&matrix[0].length==N){
            for(int i = 0; i<matrix.length; i++){
                for(int j = i; j<matrix[0].length; j++){
                    int temp = 0;
                    temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
            for(int i =0 ; i<matrix.length; i++){
                for(int j = 0; j<matrix.length/2; j++){
                    int temp = 0;
                    temp = matrix[i][j];
                    matrix[i][j] = matrix[i][matrix.length-1-j];
                    matrix[i][matrix.length-1-j] = temp;
                }
            }
        }
    }
}

同一解法的优化版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // Reverse
    for (int i = 0; i < n / 2; ++i) {
        int j = n - 1 - i;
        int[] cache = matrix[i];
        matrix[i] = matrix[j];
        matrix[j] = cache;
    }
    // Transpose
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int cache = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = cache;
        }
    }
}

解法二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2; ++i) {
        int j = n - 1 - i;
        for (int p = i; p < j; ++p) {
            int q = n - 1 - p;
            int cache = matrix[i][p];
            matrix[i][p] = matrix[q][i];
            matrix[q][i] = matrix[j][q];
            matrix[j][q] = matrix[p][j];
            matrix[p][j] = cache;
        }
    }
}

Reference

Rotate Image #48 - LeetCode

LeetCode : Rotate Image #48 - GitHub