跳到主要内容

Rotate Image

描述

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

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

分析

首先想到,纯模拟,从外到内一圈一圈的转,但这个方法太慢。

如下图,首先沿着副对角线翻转一次,然后沿着水平中线翻转一次。

Rotate image

或者,首先沿着水平中线翻转一次,然后沿着主对角线翻转一次。

代码 1

// Rotate Image
// 思路 1,时间复杂度O(n^2),空间复杂度O(1)
public class Solution {
public void rotate(final int[][] matrix) {
final int n = matrix.length;

for (int i = 0; i < n; ++i) // 沿着副对角线反转
for (int j = 0; j < n - i; ++j)
swap(matrix, i, j, n - 1 - j, n - 1 - i);

for (int i = 0; i < n / 2; ++i) // 沿着水平中线反转
for (int j = 0; j < n; ++j)
swap(matrix, i, j, n - 1 - i, j);
}
private static void swap(final int[][] matrix,
int i, int j, int p, int q) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[p][q];
matrix[p][q] = tmp;
}
};

代码 2

// Rotate Image
// 思路 2,时间复杂度O(n^2),空间复杂度O(1)
public class Solution {
public void rotate(final int[][] matrix) {
final int n = matrix.length;

for (int i = 0; i < n / 2; ++i) // 沿着水平中线反转
for (int j = 0; j < n; ++j)
swap(matrix, i, j, n - 1 - i, j);

for (int i = 0; i < n; ++i) // 沿着主对角线反转
for (int j = i + 1; j < n; ++j)
swap(matrix, i, j, j, i);
}
private static void swap(final int[][] matrix,
int i, int j, int p, int q) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[p][q];
matrix[p][q] = tmp;
}
};