受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呢?
当前回答
从线性的角度来看，考虑以下矩阵:
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);
}
}
}
其他回答
O(n²)时间和O(1)空间算法(没有任何变通方法和恶作剧的东西!)
旋转+90:
转置 反转每行
旋转-90:
方法一:
转置 反转每一列
方法二:
反转每行 转置
旋转180度:
方法一:旋转+90两次
方法2:反转每行，然后反转每列(转置)
旋转-180度:
方法一:旋转-90度2次
方法二:先反转每一列，再反转每一行
方法三:旋转+180，因为它们是相同的
#转置是Ruby的Array类的标准方法，因此:
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
实现是一个用c写的n^2转置函数，你可以在这里看到: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose 通过选择“点击切换源”旁边的“转置”。
我记得比O(n^2)的解更好，但只适用于特殊构造的矩阵(如稀疏矩阵)
一些人已经举了一些例子，其中涉及到创建一个新数组。
还有一些需要考虑的事情:
(a)不实际移动数据，只需以不同的方式遍历“旋转”的数组。
(b)就地轮换可能有点棘手。您需要一点空白的地方(大概相当于一行或一列的大小)。有一篇古老的ACM论文是关于进行原地转置的(http://doi.acm.org/10.1145/355719.355729)，但是他们的示例代码是令人讨厌的充满goto的FORTRAN。
附录:
http://doi.acm.org/10.1145/355611.355612是另一种更优越的就地转置算法。
c#代码将[n,m] 2D数组向右旋转90度
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
结果:
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
原地旋转不可能比O(n²)更快，原因是如果我们想旋转矩阵，我们必须至少一次触及所有n²元素，无论你实现什么算法。
