受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).

其他回答

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

顺时针或逆时针旋转2D数组的常用方法。

顺时针旋转 首先颠倒上下,然后交换对称 1 2 3 7 8 9 7 4 4 5 6 => 4 5 6 => 8 5 7 8 9 1 2 3 9 6 3

void rotate(vector<vector<int> > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

逆时针方向旋转 首先从左到右反向,然后交换对称 1 2 3 3 2 1 3 6 9 4 5 6 => 6 5 4 => 2 5 7 8 9 9 8 7 1 4 7

void anti_rotate(vector<vector<int> > &matrix) {
    for (auto vi : matrix) reverse(vi.begin(), vi.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

这是将数组旋转90度的简单C代码。希望这能有所帮助。

#include <stdio.h>

void main(){
int arr[3][4] =     {85, 2, 85,  4,
                     85, 6,  7, 85,
                     9, 85, 11, 12};


int arr1[4][3];

int i = 0, j = 0;

for(i=0;i<4;i++){
int k = 2;//k = (number of columns in the new array arr1 - 1)
for(j=0;j<3;j++){
arr1[i][j]=arr[k][i];
k--;
}
}

int l, m;
for(l=0;l<4;l++){
for(m=0;m<3;m++){
printf("%d ", arr1[l][m]);
}
printf("\n");
}
}//end main

O(1)内存算法:

旋转最外层的数据,然后你可以得到以下结果: [3] [9] [5] [1] [4] [6] [7] [2] [5] [0] [1] [3] [6] [2] [8] [4]

做这个旋转,我们知道

    dest[j][n-1-i] = src[i][j]

观察下图: A (0,0) -> A (0,3) A (0,3) -> A (3,3) A (3,3) -> A (3,0) A (3,0) -> A (0,0)

因此它是一个圆,你可以在一个循环中旋转N个元素。做这个N-1循环,然后你可以旋转最外层的元素。

对于2X2,内部也是一样的问题。

因此,我们可以得出如下结论:

function rotate(array, N)
{
    Rotate outer-most data
    rotate a new array with N-2 or you can do the similar action following step1
}
private static int[][] rotate(int[][] matrix, int n) {
    int[][] rotated = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rotated[i][j] = matrix[n-j-1][i];
        }
    }
    return rotated;
}