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

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

其他回答

你可以通过3个简单步骤做到这一点:

1)假设我们有一个矩阵

   1 2 3
   4 5 6
   7 8 9

2)求矩阵的转置

   1 4 7
   2 5 8
   3 6 9

3)交换行得到旋转矩阵

   3 6 9
   2 5 8
   1 4 7

Java源代码:

public class MyClass {

    public static void main(String args[]) {
        Demo obj = new Demo();
        /*initial matrix to rotate*/
        int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[][] transpose = new int[3][3]; // matrix to store transpose

        obj.display(matrix);              // initial matrix

        obj.rotate(matrix, transpose);    // call rotate method
        System.out.println();
        obj.display(transpose);           // display the rotated matix
    }
}

class Demo {   
    public void rotate(int[][] mat, int[][] tran) {

        /* First take the transpose of the matrix */
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat.length; j++) {
                tran[i][j] = mat[j][i]; 
            }
        }

        /*
         * Interchange the rows of the transpose matrix to get rotated
         * matrix
         */
        for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
            for (int k = 0; k < tran.length; k++) {
                swap(i, k, j, k, tran);
            }
        }
    }

    public void swap(int a, int b, int c, int d, int[][] arr) {
        int temp = arr[a][b];
        arr[a][b] = arr[c][d];
        arr[c][d] = temp;    
    }

    /* Method to display the matrix */
    public void display(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

输出:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 

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

@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();
}

这是一个Javascript解决方案:

const transpose = m => m[0].map((x,i) => m.map(x => x[i]));

a: // original matrix
123
456
789

transpose(a).reverse(); // rotate 90 degrees counter clockwise 
369
258
147

transpose(a.slice().reverse()); // rotate 90 degrees clockwise 
741
852
963

transpose(transpose(a.slice().reverse()).slice().reverse())
// rotate 180 degrees 
987
654
321
#!/usr/bin/env python

original = [ [1,2,3],
             [4,5,6],
             [7,8,9] ]

# Rotate matrix 90 degrees...
for i in map(None,*original[::-1]):
    print str(i) + '\n'

这导致双方旋转90度(即。123(上面)现在是741(左边)。

这个Python解决方案是可行的,因为它使用了带负步的切片来反转行顺序(将7移到最上面)

original = [ [7,8,9],
             [4,5,6],
             [1,2,3] ]

然后,它使用map(以及隐含的标识函数,这是map以None作为第一个参数的结果)和*按顺序解包所有元素,重新组合列(即。第一个元素一起放在一个元组中,第二个元素一起放在一个元组中,以此类推)。你有效地得到得到返回如下重组:

original = [[7,8,9],
             [4,5,6],
             [1,2,3]]

在原地顺时针90度旋转使用矢量矢量..

 #include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
 //Rotate a Matrix by 90 degrees
void rotateMatrix(vector<vector<int> > &matrix){
   int n=matrix.size();
   for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
        swap(matrix[i][j],matrix[j][i]);
    }
 }
     for(int i=0;i<n;i++){
        reverse(matrix[i].begin(),matrix[i].end());
       }
   }

    int main(){

   int n;
   cout<<"enter the size of the matrix:"<<endl;
     while (cin >> n) {
    vector< vector<int> > m;
      cout<<"enter the elements"<<endl;
    for (int i = 0; i < n; i++) {
        m.push_back(vector<int>(n));
        for (int j = 0; j < n; j++)
            scanf("%d", &m[i][j]);
    }
      cout<<"the rotated matrix is:"<<endl;
      rotateMatrix(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << m[i][j] << ' ';
        cout << endl;
    }
   }
   return 0;
 }