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


当前回答

原地旋转不可能比O(n²)更快,原因是如果我们想旋转矩阵,我们必须至少一次触及所有n²元素,无论你实现什么算法。

其他回答

时间- O(N),空间- O(1)

public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2; i++) {
        int last = n - 1 - i;
        for (int j = i; j < last; j++) {
            int top = matrix[i][j];
            matrix[i][j] = matrix[last - j][i];
            matrix[last - j][i] = matrix[last][last - j];
            matrix[last][last - j] = matrix[j][last];
            matrix[j][last] = top;
        }
    }
}

你可以通过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 

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

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

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

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

附录:

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

在python中:

import numpy as np

a = np.array(
    [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 0, 1, 2],
        [3, 4, 5, 6]
    ]
)

print(a)
print(b[::-1, :].T)

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

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