受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呢?
当前回答
Javascript解决NxN矩阵与运行时O(N^2)和内存O(1)
function rotate90(matrix){
var length = matrix.length
for(var row = 0; row < (length / 2); row++){
for(var col = row; col < ( length - 1 - row); col++){
var tmpVal = matrix[row][col];
for(var i = 0; i < 4; i++){
var rowSwap = col;
var colSwap = (length - 1) - row;
var poppedVal = matrix[rowSwap][colSwap];
matrix[rowSwap][colSwap] = tmpVal;
tmpVal = poppedVal;
col = colSwap;
row = rowSwap;
}
}
}
}
其他回答
PHP解决方案为顺时针和逆时针
$aMatrix = array(
array( 1, 2, 3 ),
array( 4, 5, 6 ),
array( 7, 8, 9 )
);
function CounterClockwise( $aMatrix )
{
$iCount = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $iCount - $x - 1 ][ $y ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}
function Clockwise( $aMatrix )
{
$iCount = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $x ][ $iCount - $y - 1 ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}
function printMatrix( $aMatrix )
{
$iCount = count( $aMatrix );
for( $x = 0; $x < $iCount; ++$x )
{
for( $y = 0; $y < $iCount; ++$y )
{
echo $aMatrix[ $x ][ $y ];
echo " ";
}
echo "\n";
}
}
printMatrix( $aMatrix );
echo "\n";
$aNewMatrix = CounterClockwise( $aMatrix );
printMatrix( $aNewMatrix );
echo "\n";
$aNewMatrix = Clockwise( $aMatrix );
printMatrix( $aNewMatrix );
PHP:
array_unshift($array, null);
$array = call_user_func_array("array_map", $array);
如果你需要旋转矩形二维阵列90度，在上面的代码之前或之后添加以下一行(取决于你需要的旋转方向):
$array = array_reverse($array);
哦，伙计。我一直认为这是一个“我很无聊，我能思考什么”的谜题。我想出了我的原地换位码，但到了这里发现你的和我的几乎一模一样……啊,好。这里是Ruby版本。
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
虽然旋转数据可能是必要的(也许是为了更新物理存储的表示)，但在数组访问上添加一层间接层(也许是一个接口)会变得更简单，可能更性能:
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.
与所有性能问题一样，测量，测量，测量!
下面是一个c#静态泛型方法，它可以为您完成这项工作。变量的名称很好，所以您可以很容易地理解算法的思想。
private static T[,] Rotate180 <T> (T[,] matrix)
{
var height = matrix.GetLength (0);
var width = matrix.GetLength (1);
var answer = new T[height, width];
for (int y = 0; y < height / 2; y++)
{
int topY = y;
int bottomY = height - 1 - y;
for (int topX = 0; topX < width; topX++)
{
var bottomX = width - topX - 1;
answer[topY, topX] = matrix[bottomY, bottomX];
answer[bottomY, bottomX] = matrix[topY, topX];
}
}
if (height % 2 == 0)
return answer;
var centerY = height / 2;
for (int leftX = 0; leftX < Mathf.CeilToInt(width / 2f); leftX++)
{
var rightX = width - 1 - leftX;
answer[centerY, leftX] = matrix[centerY, rightX];
answer[centerY, rightX] = matrix[centerY, leftX];
}
return answer;
}
