受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#代码，可以为任何大小的矩阵实现O(1)矩阵旋转。为了简洁性和可读性，没有错误检查或范围检查。代码:
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
好的，我把手举起来，当旋转时，它实际上不会对原始数组做任何修改。但是，在面向对象系统中，只要对象看起来像是被旋转到类的客户端，这就无关紧要了。目前，Matrix类使用对原始数组数据的引用，因此改变m1的任何值也将改变m2和m3。对构造函数稍加更改，创建一个新数组并将值复制到该数组中，就可以将其整理出来。
其他回答
JavaScript解决方案旋转矩阵90度的地方:
function rotateBy90(m) {
var length = m.length;
//for each layer of the matrix
for (var first = 0; first < length >> 1; first++) {
var last = length - 1 - first;
for (var i = first; i < last; i++) {
var top = m[first][i]; //store top
m[first][i] = m[last - i][first]; //top = left
m[last - i][first] = m[last][last - i]; //left = bottom
m[last][last - i] = m[i][last]; //bottom = right
m[i][last] = top; //right = top
}
}
return m;
}
虽然旋转数据可能是必要的(也许是为了更新物理存储的表示)，但在数组访问上添加一层间接层(也许是一个接口)会变得更简单，可能更性能:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
如果你的矩阵已经实现了这个接口，那么它可以通过这样一个装饰器类来旋转:
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
旋转+90/-90/180度，水平/垂直翻转和缩放都可以以这种方式实现。
Performance would need to be measured in your specific scenario. However the O(n^2) operation has now been replaced with an O(1) call. It's a virtual method call which is slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it's used once, then this approach would definitely win. If it's rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost.
与所有性能问题一样，测量，测量，测量!
当前所有的解决方案都有O(n^2)开销作为临时空间(这不包括那些肮脏的OOP骗子!)这里有一个内存占用为O(1)的解决方案，将矩阵原地右转90度。该死的延展性，这玩意儿跑得很快!
#include <algorithm>
#include <cstddef>
// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
for(size_t i = 0; i < N; ++i)
for(size_t j = 0; j <= (N-i); ++j)
std::swap(matrix[i][j], matrix[j][i]);
}
免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!
试试我图书馆的算盘——常见的:
@Test
public void test_42519() throws Exception {
final IntMatrix matrix = IntMatrix.range(0, 16).reshape(4);
N.println("======= original =======================");
matrix.println();
// print out:
// [0, 1, 2, 3]
// [4, 5, 6, 7]
// [8, 9, 10, 11]
// [12, 13, 14, 15]
N.println("======= rotate 90 ======================");
matrix.rotate90().println();
// print out:
// [12, 8, 4, 0]
// [13, 9, 5, 1]
// [14, 10, 6, 2]
// [15, 11, 7, 3]
N.println("======= rotate 180 =====================");
matrix.rotate180().println();
// print out:
// [15, 14, 13, 12]
// [11, 10, 9, 8]
// [7, 6, 5, 4]
// [3, 2, 1, 0]
N.println("======= rotate 270 ======================");
matrix.rotate270().println();
// print out:
// [3, 7, 11, 15]
// [2, 6, 10, 14]
// [1, 5, 9, 13]
// [0, 4, 8, 12]
N.println("======= transpose =======================");
matrix.transpose().println();
// print out:
// [0, 4, 8, 12]
// [1, 5, 9, 13]
// [2, 6, 10, 14]
// [3, 7, 11, 15]
final IntMatrix bigMatrix = IntMatrix.range(0, 10000_0000).reshape(10000);
// It take about 2 seconds to rotate 10000 X 10000 matrix.
Profiler.run(1, 2, 3, "sequential", () -> bigMatrix.rotate90()).printResult();
// Want faster? Go parallel. 1 second to rotate 10000 X 10000 matrix.
final int[][] a = bigMatrix.array();
final int[][] c = new int[a[0].length][a.length];
final int n = a.length;
final int threadNum = 4;
Profiler.run(1, 2, 3, "parallel", () -> {
IntStream.range(0, n).parallel(threadNum).forEach(i -> {
for (int j = 0; j < n; j++) {
c[i][j] = a[n - j - 1][i];
}
});
}).printResult();
}
从线性的角度来看，考虑以下矩阵:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
现在求A
1 4 7
A' = 2 5 8
3 6 9
考虑A'对B的作用，或B对A'的作用。 分别为:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
