箱猫日和

NxN矩阵顺时针旋转90度

是一个面试题，我想了好久，果然好久不做类似算法题的话会思维迟钝。题目还有一个条件是每个点用4 bytes存储，实际上是每个点是int类型的暗示，这个矩阵就是int[][]的结构。

我是先考虑点的旋转规律的，用了一点三角函数和计算机图形学的坐标变换，实际上归纳法也是可以的，只是我没找出规律。之后是实际编码，比想象中要麻烦一些，和参考答案也是有点不同的。

首先说下变化规律，计算机坐标系下(x, y)点顺时针旋转90度后结果是(y, n – x），通过多次数据归纳也可以做，以下是图形学上的证明：

-------------------->
|     (x, y)
|
|
|             (y, n - x)
|
v

计算机坐标系是左上角为原点，向右扩展x，向下扩展y。普通坐标系是

            ^
            |
   A(x, y)  | B(?, ?)
         \  | /
-------------------------->
            |
            |
            |

如果放在普通坐标系下，B的坐标是(Rsina, Rcosa)，R是半径，a是B-原点和x轴的夹角。假设A顺时针旋转90度到B，那么A点坐标是(Rsin(a+90), Rcos(a+90)。这里要用到初中学的三角函数了，可惜我忘得差不多了。查了下结果是

sin(a+90) = sina cos90 + cosa sin90 = cosa
cos(a+90) = cosa cos90 – sina sin90 = -sina

换句话说(Rsin(a+90), Rcos(a+90)) = (Rcosa, -Rsina)，如果原先(Rsina, Rcosa)定义为(x, y)的话，那么A点坐标为（y, -x)。
这里论证的是常规坐标下，实际要从计算机坐标系->常规坐标系->计算机坐标系。这里的转换其实没那么难，就是坐标系的平移（加减delta）和镜像（正负号）。举个具体例子，原先计算机坐标系为(a, b)的点，变成常规坐标系后坐标为（a – n / 2, -(b – n / 2))，这里包括两个操作：平移和镜像。
现在我们按照上面旋转90度的公式和坐标变换的公式可以得到：

  计算机坐标系 常规坐标系
A（变换后的点） 1 (x, y) 2 (x – n / 2, n / 2 – y)
B（原始点) 4 (y, n – x) 3 (y – n / 2, x – n /2)

注意，这里按照1，2，3，4的方式看的话容易理解。另外这里论证的是目标点是(x, y)，原始点的位置，如果你逆向推理，原始点是(x, y)，那么目标点也恰好是（y, n – x）。

论证了变换规律之后，实际编码还有另外一个问题：你不能按照二维扫描的方式旋转，原题其实还有个条件是in place即就地旋转。其实这块我没仔细考虑，在阅读了参考答案之后明白还有这么一茬。参考答案中给的方法是类似蛋卷的方式，先变换周围一圈，再内圈。变换圈的时候4条边轮换，(y, n – x)的点被变换到(x, y)上。这里其实还有一个细节，是int[][] matrix下matrix[a][b]对应是(b, a)不是(a, b)，所以要变换matrix[n – x][y]到matrix[y][x]。同时还有一个数组是从零开始计数的，所以这里n实际上要减去1，所以最终的代码如下：

private static void rotate(int[][] matrix, int n) {
  for (int layer = 0; layer < n / 2; layer++) {
    for (int x = layer; x < n - layer - 1; x++) {
      int value = matrix[layer][x];
      matrix[layer][x] = matrix[n - x - 1][layer];
      matrix[n - x - 1][layer] = matrix[n - layer - 1][n - x - 1];
      matrix[n - layer - 1][n - x - 1] = matrix[x][n - layer - 1];
      matrix[x][n - layer - 1] = value;
    }
  }
}

同时附上参考答案：

public static void rotate(int[][] matrix, int n) {
  for (int layer = 0; layer < n / 2; ++layer) {
    int first = layer;
    int last = n - 1 - layer;
    for(int i = first; i < last; ++i) {
      int offset = i - first;
      int top = matrix[first][i]; // save top
      // left -> top
      matrix[first][i] = matrix[last-offset][first];       
      // bottom -> left
      matrix[last-offset][first] = matrix[last][last - offset];
      // right -> bottom
      matrix[last][last - offset] = matrix[i][last];
    } 
  } 
}

xnnyygn

, ,