NxN矩阵顺时针旋转90度

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

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

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

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

如果放在普通坐标系下,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,所以最终的代码如下:

同时附上参考答案: