受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呢?


当前回答

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 );

其他回答

下面是一个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;
}

一些人已经举了一些例子,其中涉及到创建一个新数组。

还有一些需要考虑的事情:

(a)不实际移动数据,只需以不同的方式遍历“旋转”的数组。

(b)就地轮换可能有点棘手。您需要一点空白的地方(大概相当于一行或一列的大小)。有一篇古老的ACM论文是关于进行原地转置的(http://doi.acm.org/10.1145/355719.355729),但是他们的示例代码是令人讨厌的充满goto的FORTRAN。

附录:

http://doi.acm.org/10.1145/355611.355612是另一种更优越的就地转置算法。

这是我在C中的就地实现

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}

当前所有的解决方案都有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]);
}

免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!

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)的中心从左上角移动到右上角。你只是简单地从一个转置到另一个。