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

Figure: Rotate image

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

代码1

  1. // Rotate Image
  2. // 思路 1，时间复杂度O(n^2)，空间复杂度O(1)
  3. public class Solution {
  4.     public void rotate(final int[][] matrix) {
  5.         final int n = matrix.length;
  7.         for (int i = 0; i < n; ++i)  // 沿着副对角线反转
  8.             for (int j = 0; j < n - i; ++j)
  9.                 swap(matrix, i, j, n - 1 - j, n - 1 - i);
  11.         for (int i = 0; i < n / 2; ++i) // 沿着水平中线反转
  12.             for (int j = 0; j < n; ++j)
  13.                 swap(matrix, i, j, n - 1 - i, j);
  14.     }
  15.     private static void swap(final int[][] matrix, 
  16.             int i, int j, int p, int q) {
  17.         int tmp = matrix[i][j];
  18.         matrix[i][j] = matrix[p][q];
  19.         matrix[p][q] = tmp;
  20.     }
  21. };

代码2

  1. // Rotate Image
  2. // 思路 2，时间复杂度O(n^2)，空间复杂度O(1)
  3. public class Solution {
  4.     public void rotate(final int[][] matrix) {
  5.         final int n = matrix.length;
  7.         for (int i = 0; i < n / 2; ++i) // 沿着水平中线反转
  8.             for (int j = 0; j < n; ++j)
  9.                 swap(matrix, i, j, n - 1 - i, j);
  11.         for (int i = 0; i < n; ++i)  // 沿着主对角线反转
  12.             for (int j = i + 1; j < n; ++j)
  13.                 swap(matrix, i, j, j, i);
  14.     }
  15.     private static void swap(final int[][] matrix, 
  16.             int i, int j, int p, int q) {
  17.         int tmp = matrix[i][j];
  18.         matrix[i][j] = matrix[p][q];
  19.         matrix[p][q] = tmp;
  20.     }
  21. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/rotate-image.html