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


当前回答

虽然旋转数据可能是必要的(也许是为了更新物理存储的表示),但在数组访问上添加一层间接层(也许是一个接口)会变得更简单,可能更性能:

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.

与所有性能问题一样,测量,测量,测量!

其他回答

试试我图书馆的算盘——常见的:

@Test
public void test_42519() throws Exception {
    final IntMatrix matrix = IntMatrix.range(0, 16).reshape(4);

    N.println("======= original =======================");
    matrix.println();
    // print out:
    //    [0, 1, 2, 3]
    //    [4, 5, 6, 7]
    //    [8, 9, 10, 11]
    //    [12, 13, 14, 15]

    N.println("======= rotate 90 ======================");
    matrix.rotate90().println();
    // print out:
    //    [12, 8, 4, 0]
    //    [13, 9, 5, 1]
    //    [14, 10, 6, 2]
    //    [15, 11, 7, 3]

    N.println("======= rotate 180 =====================");
    matrix.rotate180().println();
    // print out:
    //    [15, 14, 13, 12]
    //    [11, 10, 9, 8]
    //    [7, 6, 5, 4]
    //    [3, 2, 1, 0]

    N.println("======= rotate 270 ======================");
    matrix.rotate270().println();
    // print out:
    //    [3, 7, 11, 15]
    //    [2, 6, 10, 14]
    //    [1, 5, 9, 13]
    //    [0, 4, 8, 12]

    N.println("======= transpose =======================");
    matrix.transpose().println();
    // print out:
    //    [0, 4, 8, 12]
    //    [1, 5, 9, 13]
    //    [2, 6, 10, 14]
    //    [3, 7, 11, 15]

    final IntMatrix bigMatrix = IntMatrix.range(0, 10000_0000).reshape(10000);

    // It take about 2 seconds to rotate 10000 X 10000 matrix.
    Profiler.run(1, 2, 3, "sequential", () -> bigMatrix.rotate90()).printResult();

    // Want faster? Go parallel. 1 second to rotate 10000 X 10000 matrix.
    final int[][] a = bigMatrix.array();
    final int[][] c = new int[a[0].length][a.length];
    final int n = a.length;
    final int threadNum = 4;

    Profiler.run(1, 2, 3, "parallel", () -> {
        IntStream.range(0, n).parallel(threadNum).forEach(i -> {
            for (int j = 0; j < n; j++) {
                c[i][j] = a[n - j - 1][i];
            }
        });
    }).printResult();
}

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
}

这是c#的

int[,] array = new int[4,4] {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,0,1,2 },
    { 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}

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

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

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

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

附录:

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

#include <iostream>
#include <iomanip>

using namespace std;
const int SIZE=3;
void print(int a[][SIZE],int);
void rotate(int a[][SIZE],int);

void main()
{
    int a[SIZE][SIZE]={{11,22,33},{44,55,66},{77,88,99}};
    cout<<"the array befor rotate\n";

    print(a,SIZE);
    rotate( a,SIZE);
    cout<<"the array after rotate\n";
    print(a,SIZE);
    cout<<endl;

}

void print(int a[][SIZE],int SIZE)
{
    int i,j;
    for(i=0;i<SIZE;i++)
       for(j=0;j<SIZE;j++)
          cout<<a[i][j]<<setw(4);
}

void rotate(int a[][SIZE],int SIZE)
{
    int temp[3][3],i,j;
    for(i=0;i<SIZE;i++)
       for(j=0;j<SIZE/2.5;j++)
       {
           temp[i][j]= a[i][j];
           a[i][j]= a[j][SIZE-i-1] ;
           a[j][SIZE-i-1] =temp[i][j];

       }
}