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


当前回答

这个解决方案不关心正方形或矩形的尺寸,你可以旋转4x5或5x4甚至4x4,它也不关心大小。 注意,这种实现在每次调用rotate90方法时都会创建一个新数组,它根本不会改变原始数组。

public static void main(String[] args) {
    int[][] a = new int[][] { 
                    { 1, 2, 3, 4 }, 
                    { 5, 6, 7, 8 }, 
                    { 9, 0, 1, 2 }, 
                    { 3, 4, 5, 6 }, 
                    { 7, 8, 9, 0 } 
                  };
    int[][] rotate180 = rotate90(rotate90(a));
    print(rotate180);
}

static int[][] rotate90(int[][] a) {
    int[][] ret = new int[a[0].length][a.length];
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            ret[j][a.length - i - 1] = a[i][j];
        }
    }
    return ret;
}

static void print(int[][] array) {
    for (int i = 0; i < array.length; i++) {
        System.out.print("[");
        for (int j = 0; j < array[i].length; j++) {
            System.out.print(array[i][j]);
            System.out.print(" ");
        }
        System.out.println("]");
    }
}

其他回答

你可以通过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();
}

从线性的角度来看,考虑以下矩阵:

    1 2 3        0 0 1
A = 4 5 6    B = 0 1 0
    7 8 9        1 0 0

现在求A

     1 4 7
A' = 2 5 8
     3 6 9

考虑A'对B的作用,或B对A'的作用。 分别为:

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
      9 6 3          1 4 7

这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:

void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
    mat[r1][c1] ^= mat[r2][c2];
    mat[r2][c2] ^= mat[r1][c1];
    mat[r1][c1] ^= mat[r2][c2];
}

void transpose(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = (i + 1); j < size; j++)
        {
            swapInSpace(mat, i, j, j, i);
        }
    }
}

void rotate(int** mat, int size)
{
    //Get transpose
    transpose(mat, size);

    //Swap columns
    for (int i = 0; i < size / 2; i++)
    {
        for (int j = 0; j < size; j++)
        {
            swapInSpace(mat, i, j, size - (i + 1), j);
        }
    }
}

我的c#示例代码的伟大算法发送@dimple:

/* Author: Dudi,
 * http://www.tutorialspoint.com/compile_csharp_online.php?PID=0Bw_CjBb95KQMYm5qU3VjVGNuZFU */

using System.IO;
using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("Rotating this matrix by 90+ degree:");

        int[,] values=new int[3,3]{{1,2,3}, {4,5,6}, {7,8,9}};
        //int[,] values=new int[4,4]{{101,102,103, 104}, {105,106, 107,108}, {109, 110, 111, 112}, {113, 114, 115, 116}};

        print2dArray(ref values);
        transpose2dArray(ref values);
        //print2dArray(ref values);
        reverse2dArray(ref values);
        Console.WriteLine("Output:");
        print2dArray(ref values);
    }

    static void print2dArray(ref int[,] matrix){
        int  nLen = matrix.GetLength(0);
        int  mLen = matrix.GetLength(1);    
        for(int n=0; n<nLen; n++){
            for(int m=0; m<mLen; m++){
                Console.Write(matrix[n,m] +"\t");
            }
            Console.WriteLine();        
        }
        Console.WriteLine();
    }

    static void transpose2dArray(ref int[,] matrix){
        int  nLen = matrix.GetLength(0);
        int  mLen = matrix.GetLength(1);    
        for(int n=0; n<nLen; n++){
            for(int m=0; m<mLen; m++){
                if(n>m){
                    int tmp = matrix[n,m];
                    matrix[n,m] = matrix[m,n];
                    matrix[m,n] = tmp;
                }
            }
        }
    }

    static void reverse2dArray(ref int[,] matrix){
        int  nLen = matrix.GetLength(0);
        int  mLen = matrix.GetLength(1);
        for(int n=0; n<nLen; n++){
            for(int m=0; m<mLen/2; m++){                
                int tmp = matrix[n,m];
                matrix[n,m] = matrix[n, mLen-1-m];
                matrix[n,mLen-1-m] = tmp;
            }
        }
    }
}

/*
Rotating this matrix by 90+ degree:                                                                                                                                             
1       2       3                                                                                                                                                               
4       5       6                                                                                                                                                               
7       8       9                                                                                                                                                               

Output:                                                                                                                                                                         
7       4       1                                                                                                                                                               
8       5       2                                                                                                                                                               
9       6       3  
*/

PHP:

array_unshift($array, null);
$array = call_user_func_array("array_map", $array);

如果你需要旋转矩形二维阵列90度,在上面的代码之前或之后添加以下一行(取决于你需要的旋转方向):

$array = array_reverse($array);