Leetcode-48: Rotate Image

[zeqing-guo]

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?

My Solution

代码的run time是0ms (25.09%)，时间复杂度是，空间复杂度是。

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int halfN = n >> 1;

        for (int i = 0; i < halfN; ++i) {
            for (int j = i; j < n - 1 - i; ++j) {
                int symI = n - 1 - i;
                int symJ = n - 1 - j;
                int temp = matrix[i][j];
                matrix[i][j] = matrix[symJ][i];
                matrix[symJ][i] = matrix[symI][symJ];
                matrix[symI][symJ] = matrix[j][symI];
                matrix[j][symI] = temp;
            }
        }
    }
}

Analysis

题目有in place的要求。首先要意识到90°的旋转变换可以转化为一次中轴对称变换加上一次对角线轴对称变换。因此可以直接用两次轴对称变换替代旋转变换：

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int halfN = n >> 1;

        for (int i = 0; i < halfN; ++i) {
            for (int j = i; j < n - 1 - i; ++j) {
                int symI = n - 1 - i;
                int symJ = n - 1 - j;
                int temp = matrix[i][j];
                matrix[i][j] = matrix[symJ][i];
                matrix[symJ][i] = matrix[symI][symJ];
                matrix[symI][symJ] = matrix[j][symI];
                matrix[j][symI] = temp;
            }
        }
    }
}

这样写代码的 run time 是1 ms。改进的话可以同时旋转四个点：

a b c d e f g h i j k l m n o p

如上面例子所示，in place需要将[b, h, i, o]映射为[o, b, h, i]。所以现在要考虑的问题是如何确定这四个点的坐标关系。由于b旋转变换得到h，h旋转变换得到o，o旋转变换得到i，i旋转变换得到b，因此我们可以根据前面提到的90°旋转变换等价为两次轴对称变换得到当b的下标（坐标）为[a, b]，矩阵为n维时，h的坐标为[a, b]->[n - 1 - a, b]（第一次中轴轴对称变换）->[b, n - 1 - a]（第二次对角轴对称变换）；i, o的坐标可以使用同样的方法得到。得到了四个点的下标后就可以直接进行交换操作，以上就是我写的第一种算法的整个思路。