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. class Solution {
  4. public:
  5.     void rotate(vector<vector<int>>& matrix) {
  6.         const int n = matrix.size();
  8.         for (int i = 0; i < n; ++i)  // 沿着副对角线反转
  9.             for (int j = 0; j < n - i; ++j)
  10.                 swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);
  12.         for (int i = 0; i < n / 2; ++i) // 沿着水平中线反转
  13.             for (int j = 0; j < n; ++j)
  14.                 swap(matrix[i][j], matrix[n - 1 - i][j]);
  15.     }
  16. };

代码2

  1. // Rotate Image
  2. // 思路 2，时间复杂度O(n^2)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     void rotate(vector<vector<int>>& matrix) {
  6.         const int n = matrix.size();
  8.         for (int i = 0; i < n / 2; ++i) // 沿着水平中线反转
  9.             for (int j = 0; j < n; ++j)
  10.                 swap(matrix[i][j], matrix[n - 1 - i][j]);
  12.         for (int i = 0; i < n; ++i)  // 沿着主对角线反转
  13.             for (int j = i + 1; j < n; ++j)
  14.                 swap(matrix[i][j], matrix[j][i]);
  15.     }
  16. };

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