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


当前回答

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

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

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

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

附录:

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

其他回答

下面是一个原地旋转的数组,而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化和输出。这只适用于正方形数组,但它们可以是任何大小。内存开销等于数组中一个元素的大小,因此您可以对任意大的数组进行旋转。

int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
    for (int j = i; j < n - i - 1; j++)
    {
        tmp             = a[i][j];
        a[i][j]         = a[j][n-i-1];
        a[j][n-i-1]     = a[n-i-1][n-j-1];
        a[n-i-1][n-j-1] = a[n-j-1][i];
        a[n-j-1][i]     = tmp;
    }
}

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

基于社区wiki算法和这个转置数组的SO答案,这里是一个Swift 4版本,可以逆时针旋转一些2D数组90度。这里假设matrix是一个2D数组:

func rotate(matrix: [[Int]]) -> [[Int]] {
    let transposedPoints = transpose(input: matrix)
    let rotatedPoints = transposedPoints.map{ Array($0.reversed()) }
    return rotatedPoints
}


fileprivate func transpose<T>(input: [[T]]) -> [[T]] {
    if input.isEmpty { return [[T]]() }
    let count = input[0].count
    var out = [[T]](repeating: [T](), count: count)
    for outer in input {
        for (index, inner) in outer.enumerated() {
            out[index].append(inner)
        }
    }

    return out
}

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

下面是Java语言:

public static void rotateInPlace(int[][] m) {
    for(int layer = 0; layer < m.length/2; layer++){
        int first = layer;
        int last = m.length - 1 - first;
        for(int i = first; i < last; i ++){
            int offset = i - first;
            int top = m[first][i];
            m[first][i] = m[last - offset][first];
            m[last - offset][first] = m[last][last - offset];
            m[last][last - offset] = m[i][last];
            m[i][last] = top;
        }
    }
}