受Raymond Chen帖子的启发,假设你有一个4x4二维数组,写一个函数使它旋转90度。Raymond链接到伪代码中的解决方案,但我想看到一些真实的东西。
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
就变成:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
更新:Nick的答案是最直接的,但是有没有比n²更好的方法呢?如果矩阵是10000x10000呢?
受Raymond Chen帖子的启发,假设你有一个4x4二维数组,写一个函数使它旋转90度。Raymond链接到伪代码中的解决方案,但我想看到一些真实的东西。
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
就变成:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
更新:Nick的答案是最直接的,但是有没有比n²更好的方法呢?如果矩阵是10000x10000呢?
当前回答
基于大量的其他答案,我用c#想出了这个:
/// <param name="rotation">The number of rotations (if negative, the <see cref="Matrix{TValue}"/> is rotated counterclockwise;
/// otherwise, it's rotated clockwise). A single (positive) rotation is equivalent to 90° or -270°; a single (negative) rotation is
/// equivalent to -90° or 270°. Matrices may be rotated by 90°, 180°, or 270° only (or multiples thereof).</param>
/// <returns></returns>
public Matrix<TValue> Rotate(int rotation)
{
var result = default(Matrix<TValue>);
//This normalizes the requested rotation (for instance, if 10 is specified, the rotation is actually just +-2 or +-180°, but all
//correspond to the same rotation).
var d = rotation.ToDouble() / 4d;
d = d - (int)d;
var degree = (d - 1d) * 4d;
//This gets the type of rotation to make; there are a total of four unique rotations possible (0°, 90°, 180°, and 270°).
//Each correspond to 0, 1, 2, and 3, respectively (or 0, -1, -2, and -3, if in the other direction). Since
//1 is equivalent to -3 and so forth, we combine both cases into one.
switch (degree)
{
case -3:
case +1:
degree = 3;
break;
case -2:
case +2:
degree = 2;
break;
case -1:
case +3:
degree = 1;
break;
case -4:
case 0:
case +4:
degree = 0;
break;
}
switch (degree)
{
//The rotation is 0, +-180°
case 0:
case 2:
result = new TValue[Rows, Columns];
break;
//The rotation is +-90°
case 1:
case 3:
result = new TValue[Columns, Rows];
break;
}
for (uint i = 0; i < Columns; ++i)
{
for (uint j = 0; j < Rows; ++j)
{
switch (degree)
{
//If rotation is 0°
case 0:
result._values[j][i] = _values[j][i];
break;
//If rotation is -90°
case 1:
//Transpose, then reverse each column OR reverse each row, then transpose
result._values[i][j] = _values[j][Columns - i - 1];
break;
//If rotation is +-180°
case 2:
//Reverse each column, then reverse each row
result._values[(Rows - 1) - j][(Columns - 1) - i] = _values[j][i];
break;
//If rotation is +90°
case 3:
//Transpose, then reverse each row
result._values[i][j] = _values[Rows - j - 1][i];
break;
}
}
}
return result;
}
其中_values对应于由Matrix<TValue>定义的私有二维数组(形式为[][])。result = new TValue[Columns, Rows]可能通过隐式操作符重载并将二维数组转换为Matrix<TValue>。 Columns和Rows两个属性是公共属性,用于获取当前实例的列数和行数:
public uint Columns
=> (uint)_values[0].Length;
public uint Rows
=> (uint)_values.Length;
当然,假设您更喜欢使用无符号下标;-)
所有这些都允许您指定它应该旋转多少次,以及它应该向左旋转(如果小于零)还是向右旋转(如果大于零)。您可以改进此方法,以检查实际角度的旋转,但如果值不是90的倍数,则可能会抛出异常。有了这些输入,你可以相应地改变方法:
public Matrix<TValue> Rotate(int rotation)
{
var _rotation = (double)rotation / 90d;
if (_rotation - Math.Floor(_rotation) > 0)
{
throw new NotSupportedException("A matrix may only be rotated by multiples of 90.").
}
rotation = (int)_rotation;
...
}
Since a degree is more accurately expressed by double than int, but a matrix can only rotate in multiples of 90, it is far more intuitive to make the argument correspond to something else that can be accurately represented by the data structure used. int is perfect because it can tell you how many times to rotate it up to a certain unit (90) as well as the direction. double may very well be able to tell you that also, but it also includes values that aren't supported by this operation (which is inherently counter-intuitive).
其他回答
Nick的答案也适用于NxM阵列,只需要做一点修改(与NxN相反)。
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
考虑这个问题的一种方法是将轴(0,0)的中心从左上角移动到右上角。你只是简单地从一个转置到另一个。
在JavaScript中实现dimple的+90伪代码(例如转置然后反转每一行):
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
这是c#的
int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};
int[,] rotated = RotateMatrix(array, 4);
static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}
return ret;
}
O(n²)时间和O(1)空间算法(没有任何变通方法和恶作剧的东西!)
旋转+90:
转置 反转每行
旋转-90:
方法一:
转置 反转每一列
方法二:
反转每行 转置
旋转180度:
方法一:旋转+90两次
方法2:反转每行,然后反转每列(转置)
旋转-180度:
方法一:旋转-90度2次
方法二:先反转每一列,再反转每一行
方法三:旋转+180,因为它们是相同的
这是Java中的一个更好的版本:我已经为一个具有不同宽度和高度的矩阵制作了它
H是旋转后矩阵的高度 W是旋转后矩阵的宽度
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
此代码基于Nick Berardi的帖子。