如何旋转二维数组？

[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]

#1 楼

它在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;
}
 

#2 楼

O（n ^ 2）时间和O（1）空间算法（没有任何变通办法和手脚乱麻的东西！）

旋转+90：



转置
反转每一行

按-90旋转：

方法1：


转置
反转每列

方法2：


反转每一行
转置

旋转+180：

方法1：旋转+90两次

方法2：反转每一行，然后反转每一列（转置）

旋转-180：

方法1：旋转-90两次

方法2：反转每列，然后反转每一行

方法3：原样旋转+180相同

#3 楼

我想补充一点细节。在此答案中，重复了关键概念，步伐缓慢且有意重复。这里提供的解决方案并不是语法上最紧凑的解决方案，但是它是为希望了解什么是矩阵旋转以及最终实现的人而设计的。
首先，什么是矩阵？出于此答案的目的，矩阵只是宽度和高度相同的网格。注意，矩阵的宽度和高度可以不同，但​​是为简单起见，本教程仅考虑宽度和高度相等的矩阵（正方形矩阵）。是的，矩阵是矩阵的复数。
示例矩阵是：2×2、3×3或5×5。或者，更一般地，N×N。 2×2矩阵将具有4个正方形，因为2×2 = 4。 5×5矩阵将具有25个正方形，因为5×5 = 25。每个正方形称为元素或条目。在下图中，我们将用句点（.）表示每个元素：
2×2矩阵

. .
. .

3×3矩阵

. . .
. . .
. . .

4×4矩阵

. . . .
. . . .
. . . .
. . . .

那么，旋转矩阵是什么意思？让我们以2×2矩阵为单位，在每个元素中放置一些数字，以便观察旋转：
将其旋转90度可以得到：

0 1
2 3

整个矩阵一次向右，就像转动汽车的方向盘一样。考虑将矩阵“倾斜”到其右侧可能会有所帮助。我们想用Python编写一个函数，该函数需要一个矩阵并向右旋转一次。函数签名将是：

2 0
3 1

将使用二维数组定义矩阵：

def rotate(matrix):
    # Algorithm goes here.

因此第一个索引位置访问该行。第二个索引位置访问该列：

matrix = [
    [0,1],
    [2,3]
]

我们将定义一个实用函数来打印矩阵。

matrix[row][column]

旋转矩阵的一种方法是一次对其进行一层处理。但是什么是层？想一想洋葱。就像洋葱的各层一样，当每一层都被除去时，我们向中心移动。其他类比是俄罗斯套娃玩偶或包裹传递游戏。
矩阵的宽度和高度决定了该矩阵中的层数。让我们为每层使用不同的符号：
2×2矩阵具有1层

def print_matrix(matrix):
    for row in matrix:
        print row

3×3矩阵具有2层

. .
. .

A 4×4矩阵有2层

. . .
. x .
. . .

5×5矩阵有3层
6×6矩阵有3层

. . . .
. x x .
. x x .
. . . .

A 7× 7个矩阵有4层

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

您可能会注意到，将矩阵的宽度和高度增加1并不总是会增加层数。使用上述矩阵并制表层和尺寸，我们看到层数每增加两个宽度和高度就增加一次：

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

但是，并非所有层都需要旋转。旋转前后的1×1矩阵相同。无论整体矩阵有多大，旋转前后的中央1×1层始终是相同的：

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

给出N×N矩阵，我们如何以编程方式确定需要旋转的层数？如果将宽度或高度除以2，而忽略其余部分，则会得到以下结果。

+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 |      1 |
| 2×2 |      1 |
| 3×3 |      2 |
| 4×4 |      2 |
| 5×5 |      3 |
| 6×6 |      3 |
| 7×7 |      4 |
+-----+--------+

请注意N/2如何与需要旋转的层数匹配？有时，可旋转的层数比矩阵中的层总数少一。当最内层仅由一个元素（即1×1矩阵）形成，因此不需要旋转时，会发生这种情况。只需忽略它即可。
我们无疑会在函数中使用此信息来旋转矩阵，所以现在就添加它：

+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 |      1 |                0 |
| 2×2 |      1 |                1 |
| 3×3 |      2 |                1 |
| 4×4 |      2 |                2 |
| 5×5 |      3 |                2 |
| 6×6 |      3 |                3 |
| 7×7 |      4 |                3 |
+-----+--------+------------------+

现在我们知道了什么是层，以及如何确定实际需要旋转的层数，如何隔离单个层以便旋转？首先，我们检查从最外层向内到最内层的矩阵。 5×5矩阵共有三层，需要旋转的两层：

+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers |   N/2   |
+-----+--------+------------------+---------+
| 1×1 |      1 |                0 | 1/2 = 0 |
| 2×2 |      1 |                1 | 2/2 = 1 |
| 3×3 |      2 |                1 | 3/2 = 1 |
| 4×4 |      2 |                2 | 4/2 = 2 |
| 5×5 |      3 |                2 | 5/2 = 2 |
| 6×6 |      3 |                3 | 6/2 = 3 |
| 7×7 |      4 |                3 | 7/2 = 3 |
+-----+--------+------------------+---------+

让我们先看一下列。假设我们从0开始计数，定义最外层的列的位置是0和4：

def rotate(matrix):
    size = len(matrix)
    # Rotatable layers only.
    layer_count = size / 2

0和4也是最外层的行的位置。

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

因为宽度和高度相同，所以总是这样。因此，我们可以仅使用两个值（而不是四个）来定义层的列和行位置。
向内移动到第二层，列的位置为1和3。而且，是的，您猜对了，行也一样。重要的是要了解当向内移动到下一层时，我们必须同时增加和减少行和列的位置。

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

因此，要检查每一层，我们需要一个带有递增和递减计数器的循环表示从最外层开始向内移动。我们将其称为“层循环”。

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

上面的代码遍历需要旋转的任何层的（行和列）位置。

+-----------+---------+---------+---------+
|   Layer   |  Rows   | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes     |
| Inner     | 1 and 3 | 1 and 3 | Yes     |
| Innermost | 2       | 2       | No      |
+-----------+---------+---------+---------+

我们现在有一个循环，提供每个图层的行和列的位置。变量first和last标识第一行和最后一行和列的索引位置。再次参考我们的行表和列表：

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1
        print 'Layer %d: first: %d, last: %d' % (layer, first, last)

# 5x5 matrix
matrix = [
    [ 0, 1, 2, 3, 4],
    [ 5, 6, 6, 8, 9],
    [10,11,12,13,14],
    [15,16,17,18,19],
    [20,21,22,23,24]
]

rotate(matrix)

所以我们可以浏览矩阵的各个层。现在，我们需要一种在图层中导航的方法，以便可以在该图层中移动元素。请注意，元素永远不会从一层“跳”到另一层，但它们确实会在各自的层中移动。
旋转图层中的每个元素都会旋转整个图层。旋转矩阵中的所有图层将旋转整个矩阵。这句话非常重要，因此请在继续之前尽力理解它。
现在，我们需要一种实际移动元素的方法，即旋转每个元素，然后旋转图层，最后旋转矩阵。为简单起见，我们将还原为具有一个可旋转图层的3x3矩阵。

Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3

我们的层循环提供了第一列和最后一列以及第一行和最后一行的索引：

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

因为我们的矩阵始终是正方形，所以我们只需要两个变量first和last，因为行和列的索引位置相同。

0 1 2
3 4 5
6 7 8

变量first和last可以容易用于引用矩阵的四个角。这是因为可以使用first和last的各种排列来定义角本身（不减去，减去或偏移这些变量）：

+-----+-------+
| Col | 0 1 2 |
+-----+-------+
|     | 0 1 2 |
|     | 3 4 5 |
|     | 6 7 8 |
+-----+-------+

+-----+-------+
| Row |       |
+-----+-------+
|   0 | 0 1 2 |
|   1 | 3 4 5 |
|   2 | 6 7 8 |
+-----+-------+

因此，我们从外四点开始旋转角落-我们将首先旋转这些角落。让我们用*突出显示它们。

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Our layer loop i=0, i=1, i=2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1
        
        # We want to move within a layer here.

我们想将每个*替换为右边的*。因此，让我们继续打印仅使用first和last的各种排列定义的角落：

+---------------+-------------------+-------------+
| Corner        | Position          | 3x3 Values  |
+---------------+-------------------+-------------+
| top left      | (first, first)    | (0,0)       |
| top right     | (first, last)     | (0,2)       |
| bottom right  | (last, last)      | (2,2)       |
| bottom left   | (last, first)     | (2,0)       |
+---------------+-------------------+-------------+

输出应为：

* 1 *
3 4 5
* 7 *

现在我们可以很容易地交换每个图层循环中的拐角：

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = (first, first)
        top_right = (first, last)
        bottom_right = (last, last)
        bottom_left = (last, first)

        print 'top_left: %s' % (top_left)
        print 'top_right: %s' % (top_right)
        print 'bottom_right: %s' % (bottom_right)
        print 'bottom_left: %s' % (bottom_left)

matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]

rotate(matrix)

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):
        
        first = layer
        last = size - first - 1

        top_left = matrix[first][first]
        top_right = matrix[first][last]
        bottom_right = matrix[last][last]
        bottom_left = matrix[last][first]

        # bottom_left -> top_left
        matrix[first][first] = bottom_left
        # top_left -> top_right
        matrix[first][last] = top_left
        # top_right -> bottom_right
        matrix[last][last] = top_right
        # bottom_right -> bottom_left
        matrix[last][first] = bottom_right


print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)

太好了！我们已经成功旋转了矩阵的每个角。但是，我们尚未旋转每一层中间的元素。显然，我们需要一种在层中进行迭代的方法。
问题是，到目前为止，函数中的唯一循环（我们的层循环）在每次迭代中都移至下一层。由于我们的矩阵只有一层可旋转的图层，因此仅旋转转角后，图层循环就会退出。让我们看看使用更大的5×5矩阵（需要旋转两层）会发生什么。该功能代码已被省略，但与上面相同：

[0, 1, 2]
[3, 4, 5]
[6, 7, 8]

输出为：

[6, 1, 0]
[3, 4, 5]
[8, 7, 2]

最外面的角并不奇怪图层已旋转，但是您可能还会注意到下一层（向内）的角也已旋转。这很有道理。我们已经编写了代码来浏览各个图层，并旋转每个图层的边角。这感觉就像是进步，但不幸的是我们必须退后一步。在上一层（外层）完全旋转之前，进入下一层是不好的。也就是说，直到旋转了图层中的每个元素。只旋转角落就行了！
深呼吸。我们需要另一个循环。嵌套循环同样如此。新的嵌套循环将使用first和last变量，以及在图层内导航的偏移量。我们将此新循环称为“元素循环”。元素循环将访问位于顶部行的每个元素，位于右侧的每个元素，位于底部行的每个元素，位于左侧的每个元素。

沿顶部行向前移动需要该列
要增加索引。
向右向下移动需要增加行索引。
沿底部向后移动需要减小列
索引。 。
向左移动需要减小行索引。

这听起来很复杂，但是它很容易，因为我们递增和递减实现次数的次数。沿矩阵的所有四个边的上述值保持相同。例如：

在顶部一行移动1个元素。
在右侧向下移动1个元素。
在底部一行向后移动1个元素。
在左侧将1个元素向上移动。

这意味着我们可以在与first和last变量结合使用可在图层中移动。可能需要注意的是，越过第一行和越过右侧都需要增加。在沿着底部向左和向后向上移动时，都需要递减。

matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)

现在，我们只需要将顶部分配给右侧，将右侧分配给底部，将底部分配给左侧，然后左侧到顶部。将所有这些放在一起，我们得到：

[20,  1,  2,  3,  0]
[ 5, 16,  7,  6,  9]
[10, 11, 12, 13, 14]
[15, 18, 17,  8, 19]
[24, 21, 22, 23,  4]

给出矩阵：

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    
    # Move through layers (i.e. layer loop).
    for layer in range(0, layer_count):
        
            first = layer
            last = size - first - 1

            # Move within a single layer (i.e. element loop).
            for element in range(first, last):
            
                offset = element - first

                # 'element' increments column (across right)
                top = (first, element)
                # 'element' increments row (move down)
                right_side = (element, last)
                # 'last-offset' decrements column (across left)
                bottom = (last, last-offset)
                # 'last-offset' decrements row (move up)
                left_side = (last-offset, first)

                print 'top: %s' % (top)
                print 'right_side: %s' % (right_side)
                print 'bottom: %s' % (bottom)
                print 'left_side: %s' % (left_side)

我们的rotate函数产生：

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1

        for element in range(first, last):
            offset = element - first

            top = matrix[first][element]
            right_side = matrix[element][last]
            bottom = matrix[last][last-offset]
            left_side = matrix[last-offset][first]

            matrix[first][element] = left_side
            matrix[element][last] = top
            matrix[last][last-offset] = right_side
            matrix[last-offset][first] = bottom

#4 楼

Python：

 rotated = list(zip(*original[::-1]))
 

和逆时针：

 rotated_ccw = list(zip(*original))[::-1]
 

工作原理：

zip(*original)通过将列表中的相应项堆叠到新数组中来交换二维数组的轴列表。 （*运算符告诉函数将包含的列表分布到参数中）

>>> list(zip(*[[1,2,3],[4,5,6],[7,8,9]]))
[[1,4,7],[2,5,8],[3,6,9]]

[::-1]语句反转数组元素（请参阅扩展切片或此问题）：

>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]

最后，将两者结合将导致旋转变换。

[::-1]放置位置的变化将反转矩阵不同级别中的列表。

#5 楼

这是一个进行适当旋转的方法，而不是使用全新的数组保存结果。我放弃了数组的初始化并打印出来。这仅适用于正方形阵列，但它们可以是任何大小。内存开销等于数组一个元素的大小，因此您可以根据需要旋转一个大数组。

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

#6 楼

这里有很多好的代码，但我只想显示几何图形，以便您可以更好地理解代码逻辑。这是我的处理方法。

首先，不要将其与换位相混淆，这很容易。.

基本思想是将其视为层和层。我们一次旋转一层。

假设我们有一个4x4

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

我们将其顺时针旋转90度后得到

13  9   5   1
14  10  6   2   
15  11  7   3
16  12  8   4

所以让我们分解一下，首先我们旋转四个角

1           4


13          16

，然后旋转以下菱形有点歪斜

    2
            8
9       
        15

然后是第二颗歪斜的钻石

        3
5           
            12
    14

因此，实际上我们每次都做一个外壳，直到最后一个

中间的正方形（或者如果奇怪的是最后一个不动的元素）

6   7
10  11

所以现在让我们找出每一层的索引，假设我们总是在最外层工作，我们正在做

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

等等等等
unti我在边缘的一半处

，所以通常图案是

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

#7 楼

正如我在上一篇文章中所说的那样，这是C＃中的一些代码，该代码为任何大小矩阵实现O（1）矩阵旋转。为了简便起见，没有错误检查或范围检查。代码：

 static void Main (string [] args)
{
  int [,]
    //  create an arbitrary matrix
    m = {{0, 1}, {2, 3}, {4, 5}};

  Matrix
    //  create wrappers for the data
    m1 = new Matrix (m),
    m2 = new Matrix (m),
    m3 = new Matrix (m);

  //  rotate the matricies in various ways - all are O(1)
  m1.RotateClockwise90 ();
  m2.Rotate180 ();
  m3.RotateAnitclockwise90 ();

  //  output the result of transforms
  System.Diagnostics.Trace.WriteLine (m1.ToString ());
  System.Diagnostics.Trace.WriteLine (m2.ToString ());
  System.Diagnostics.Trace.WriteLine (m3.ToString ());
}

class Matrix
{
  enum Rotation
  {
    None,
    Clockwise90,
    Clockwise180,
    Clockwise270
  }

  public Matrix (int [,] matrix)
  {
    m_matrix = matrix;
    m_rotation = Rotation.None;
  }

  //  the transformation routines
  public void RotateClockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
  }

  public void Rotate180 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
  }

  public void RotateAnitclockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
  }

  //  accessor property to make class look like a two dimensional array
  public int this [int row, int column]
  {
    get
    {
      int
        value = 0;

      switch (m_rotation)
      {
      case Rotation.None:
        value = m_matrix [row, column];
        break;

      case Rotation.Clockwise90:
        value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
        break;

      case Rotation.Clockwise180:
        value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
        break;

      case Rotation.Clockwise270:
        value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
        break;
      }

      return value;
    }

    set
    {
      switch (m_rotation)
      {
      case Rotation.None:
        m_matrix [row, column] = value;
        break;

      case Rotation.Clockwise90:
        m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
        break;

      case Rotation.Clockwise180:
        m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
        break;

      case Rotation.Clockwise270:
        m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
        break;
      }
    }
  }

  //  creates a string with the matrix values
  public override string ToString ()
  {
    int
      num_rows = 0,
      num_columns = 0;

    switch (m_rotation)
    {
    case Rotation.None:
    case Rotation.Clockwise180:
      num_rows = m_matrix.GetUpperBound (0);
      num_columns = m_matrix.GetUpperBound (1);
      break;

    case Rotation.Clockwise90:
    case Rotation.Clockwise270:
      num_rows = m_matrix.GetUpperBound (1);
      num_columns = m_matrix.GetUpperBound (0);
      break;
    }

    StringBuilder
      output = new StringBuilder ();

    output.Append ("{");

    for (int row = 0 ; row <= num_rows ; ++row)
    {
      if (row != 0)
      {
        output.Append (", ");
      }

      output.Append ("{");

      for (int column = 0 ; column <= num_columns ; ++column)
      {
        if (column != 0)
        {
          output.Append (", ");
        }

        output.Append (this [row, column].ToString ());
      }

      output.Append ("}");
    }

    output.Append ("}");

    return output.ToString ();
  }

  int [,]
    //  the original matrix
    m_matrix;

  Rotation
    //  the current view of the matrix
    m_rotation;
}
 

好吧，我举起手来，它没有旋转时实际上不会对原始数组进行任何修改。但是，在OO系统中，只要对象看起来像已被旋转到类的客户端，都没有关系。目前，Matrix类使用对原始数组数据的引用，因此更改m1的任何值也将更改m2和m3。只需对构造函数进行一些小的更改，以创建一个新数组并将其值复制到该数组中即可。

#8 楼

虽然可能有必要旋转数据（也许更新物理存储的表示形式），但将间接层添加到数组访问（可能是接口）变得更简单，并且可能更有效：

< pre class =“ lang-csharp prettyprint-override”> interface IReadableMatrix { int GetValue(int x, int y); }

如果您的Matrix已经实现了此接口，则可以通过这样的装饰器类来旋转它：

 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度，水平/垂直翻转，缩放均可在

性能需要在您的特定情况下进行评估。但是，O（n ^ 2）操作现在已被O（1）调用所取代。这是一个虚拟方法调用，比直接访问数组要慢，因此它取决于旋转后旋转后的数组使用的频率。如果只使用一次，那么这种方法肯定会成功。如果旋转，然后在长时间运行的系统中使用了几天，则原地旋转可能会更好。这还取决于您是否可以接受前期成本。

和所有性能问题一样，请衡量，衡量，衡量！！

#9 楼

这是Java中更好的版本：我已经将其用于宽度和高度不同的矩阵


h是旋转后矩阵的高度
w是旋转后矩阵的宽度

 public int[][] rotateMatrixRight(int[][] matrix)
{
    /* W and H are already swapped */
    int w = matrix.length;
    int h = matrix[0].length;
    int[][] ret = new int[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ret[i][j] = matrix[w - j - 1][i];
        }
    }
    return ret;
}


public int[][] rotateMatrixLeft(int[][] matrix)
{
    /* W and H are already swapped */
    int w = matrix.length;
    int h = matrix[0].length;   
    int[][] ret = new int[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ret[i][j] = matrix[j][h - i - 1];
        }
    }
    return ret;
}
 

此代码基于Nick Berardi的帖子。

#10 楼

Ruby-way：.transpose.map &:reverse

#11 楼

已经有很多答案，我发现有两个声称O（1）时间复杂度。真正的O（1）算法是保持阵列存储不变，并更改索引元素的方式。这样做的目的是不消耗额外的内存，也不需要额外的时间来迭代数据。

90度，-90度和180度的旋转是简单的转换，只要您知道2D数组中有多少行和多少列；要将任何矢量旋转90度，请交换轴并取反Y轴。对于-90度，交换轴并取反X轴。对于180度，可否定两个轴而无需交换。

还可以进行其他转换，例如通过独立地否定轴来水平和/或垂直镜像。

这可以通过以下方式完成：例如访问器方法。以下示例是JavaScript函数，但是这些概念同样适用于所有语言。

  // Get an array element in column/row order
 var getArray2d = function(a, x, y) {
   return a[y][x];
 };

 //demo
 var arr = [
   [5, 4, 6],
   [1, 7, 9],
   [-2, 11, 0],
   [8, 21, -3],
   [3, -1, 2]
 ];

 var newarr = [];
 arr[0].forEach(() => newarr.push(new Array(arr.length)));

 for (var i = 0; i < newarr.length; i++) {
   for (var j = 0; j < newarr[0].length; j++) {
     newarr[i][j] = getArray2d(arr, i, j);
   }
 }
 console.log(newarr); 

 // Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
  var t = x;
  x = y;
  y = a.length - t - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCW(arr, i, j);
  }
}
console.log(newarr); 

 // Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
  var t = x;
  x = a[0].length - y - 1;
  y = t;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCCW(arr, i, j);
  }
}
console.log(newarr); 

 // Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
  x = a[0].length - x - 1;
  y = a.length - y - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2d180(arr, i, j);
  }
}
console.log(newarr); 

此代码假设一个嵌套数组的数组，其中每个内部数组都是一行。

该方法允许您读取（或写入）元素（甚至以随机顺序），就好像阵列已经旋转或变换一样。现在，只需选择正确的函数（可能是通过引用来调用）就可以了！

该概念可以扩展为通过访问器方法加性地（非破坏性地）应用转换。包括任意角度旋转和缩放。

#12 楼

几个人已经提出了涉及制作新阵列的示例。

还有一些其他要考虑的事项：

（a）除了实际移动数据外，只需以不同的方式遍历“旋转”数组即可。

（b）就地旋转可能会有些棘手。您将需要一些暂存位置（可能大约等于一行或一列的大小）。有一篇古老的ACM文章关于进行原位转置（http://doi.acm.org/10.1145/355719.355729），但是他们的示例代码是讨厌的goto-laden FORTRAN。

附录：

http://doi.acm.org/10.1145/355611.355612是另一种据称更好的原位转置算法。

#13 楼

尼克的答案也适用于NxM阵列，只需稍作修改（与NxN相对）。

 string[,] orig = new string[n, m];
string[,] rot = new string[m, n];

...

for ( int i=0; i < n; i++ )
  for ( int j=0; j < m; j++ )
    rot[j, n - i - 1] = orig[i, j];
 

考虑此问题的一种方法是，将轴（0,0）的中心从左上角移到了右上角。您只是从一个换位到另一个。

#14 楼

时间-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;
        }
    }
}

#15 楼

这是我的Ruby版本（请注意，值显示的并不相同，但仍会按照说明旋转）。

 def rotate(matrix)
  result = []
  4.times { |x|
    result[x] = []
    4.times { |y|
      result[x][y] = matrix[y][3 - x]
    }
  }

  result
end

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

def print_matrix(matrix)
  4.times { |y|
    4.times { |x|
      print "#{matrix[x][y]} "
    }
    puts ""
  }
end

print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
 

输出：

1 5 9 3 
2 6 0 4 
3 7 1 5 
4 8 2 6 

4 3 2 1 
8 7 6 5 
2 1 0 9 
6 5 4 3

#16 楼

这是java的空间旋转方法，仅适用于正方形。对于非正方形2D数组，您仍然必须创建新数组。

 private void rotateInSpace(int[][] arr) {
    int z = arr.length;
    for (int i = 0; i < z / 2; i++) {
        for (int j = 0; j < (z / 2 + z % 2); j++) {
            int x = i, y = j;
            int temp = arr[x][y];
            for (int k = 0; k < 4; k++) {
                int temptemp = arr[y][z - x - 1];
                arr[y][z - x - 1] = temp;
                temp = temptemp;

                int tempX = y;
                y = z - x - 1;
                x = tempX;
            }
        }
    }
}
 

通过创建新数组来旋转任意大小的2d数组的代码：

 private int[][] rotate(int[][] arr) {
    int width = arr[0].length;
    int depth = arr.length;
    int[][] re = new int[width][depth];
    for (int i = 0; i < depth; i++) {
        for (int j = 0; j < width; j++) {
            re[j][depth - i - 1] = arr[i][j];
        }
    }
    return re;
}
 

#17 楼

dimple的+90伪代码在JavaScript中的实现（例如转置然后反转每一行）：

 function rotate90(a){
  // transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
  a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
  // row reverse
  for (i in a){
    a[i] = a[i].reverse();
  }
  return a;
}
 

#18 楼

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

#19 楼

这是我的实现，在C，O（1）内存复杂性的情况下，顺时针旋转90度：

 #include <stdio.h>

#define M_SIZE 5

static void initMatrix();
static void printMatrix();
static void rotateMatrix();

static int m[M_SIZE][M_SIZE];

int main(void){
    initMatrix();
    printMatrix();
    rotateMatrix();
    printMatrix();

    return 0;
}

static void initMatrix(){
    int i, j;

    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            m[i][j] = M_SIZE*i + j + 1;
        }
    }
}

static void printMatrix(){
    int i, j;

    printf("Matrix\n");
    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            printf("%02d ", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

static void rotateMatrix(){
    int r, c;

    for(r = 0; r < M_SIZE/2; r++){
        for(c = r; c < M_SIZE - r - 1; c++){
            int tmp = m[r][c];

            m[r][c] = m[M_SIZE - c - 1][r];
            m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
            m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
            m[c][M_SIZE - r - 1] = tmp;
        }
    }
}
 

#20 楼

这是Java版本：

 public static void rightRotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
           int offset = i - first;
           int temp = matrix[first][i];
           matrix[first][i] = matrix[last-offset][first];
           matrix[last-offset][first] = matrix[last][last-offset];
           matrix[last][last-offset] = matrix[i][last];
           matrix[i][last] = temp;
        }
    }
}
 

该方法首先旋转最外层，然后移动依次进入内层。

#21 楼

从线性角度来看，考虑矩阵：

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

现在取一个转置

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

#22 楼

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

#23 楼

PHP：

<?php    
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result

while(count($a)>0)
{
    $b[count($a[0])-1][] = array_shift($a[0]);
    if (count($a[0])==0)
    {
         array_shift($a);
    }
}

从PHP5.6起，可以通过调用array_map()进行数组转置。换句话说，列将转换为行。

代码：（演示）

$array = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 0, 1, 2],
    [3, 4, 5, 6]
];
$transposed = array_map(null, ...$array);

$ transposed：

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

#24 楼

For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[X-i][j]

X是图形所在的数组的大小。

#25 楼

#transpose是Ruby Array类的标准方法，因此：

% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] 
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]

实现是用C编写的n ^ 2换位函数。您可以在这里看到它：
http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose
通过选择“转置”旁边的“单击以切换源”。

我记得比O（n ^ 2）解要好，但仅适用于特殊构造的矩阵（例如稀疏矩阵）

#26 楼

任意M * N矩阵的C轴顺时针旋转90度的C代码

 void rotateInPlace(int * arr[size][size], int row, int column){
    int i, j;
    int temp = row>column?row:column;
    int flipTill = row < column ? row : column;
    for(i=0;i<flipTill;i++){
        for(j=0;j<i;j++){
            swapArrayElements(arr, i, j);
        }
    }

    temp = j+1;

    for(i = row>column?i:0; i<row; i++){
            for(j=row<column?temp:0; j<column; j++){
                swapArrayElements(arr, i, j);
            }
    }

    for(i=0;i<column;i++){
        for(j=0;j<row/2;j++){
            temp = arr[i][j];
            arr[i][j] = arr[i][row-j-1];
            arr[i][row-j-1] = temp;
        }
    }
}
 

#27 楼

这是我在C中的就地实现

 void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}
 

#28 楼

这是我对矩阵进行90度旋转的尝试，这是C语言中的两步解决方案。首先将矩阵转置到位，然后交换cols。

 #define ROWS        5
#define COLS        5

void print_matrix_b(int B[][COLS], int rows, int cols) 
{
    for (int i = 0; i <= rows; i++) {
        for (int j = 0; j <=cols; j++) {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }
}

void swap_columns(int B[][COLS], int l, int r, int rows)
{
    int tmp;
    for (int i = 0; i <= rows; i++) {
        tmp = B[i][l];
        B[i][l] = B[i][r];
        B[i][r] = tmp;
    }
}


void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
    int tmp;
    // Transpose the matrix first
    for (int i = 0; i <= rows; i++) {
        for (int j = i; j <=cols; j++) {
            tmp = B[i][j];
            B[i][j] = B[j][i];
            B[j][i] = tmp;
        }
    }
    // Swap the first and last col and continue until
    // the middle.
    for (int i = 0; i < (cols / 2); i++)
        swap_columns(B, i, cols - i, rows);
}



int _tmain(int argc, _TCHAR* argv[])
{
    int B[ROWS][COLS] = { 
                  {1, 2, 3, 4, 5}, 
                      {6, 7, 8, 9, 10},
                          {11, 12, 13, 14, 15},
                          {16, 17, 18, 19, 20},
                          {21, 22, 23, 24, 25}
                        };

    matrix_2d_rotation(B, ROWS - 1, COLS - 1);

    print_matrix_b(B, ROWS - 1, COLS -1);
    return 0;
}
 

#29 楼

@dagorym：啊，伙计。我一直把它当作一个很好的“我很无聊，我能思考什么”的难题。我想出了我的就地转置代码，但到这里来发现您的代码与我的代码几乎完全相同...嗯。在Ruby中。

 require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }

pp a

0.upto(n/2-1) do |i|
  i.upto(n-i-2) do |j|
    tmp             = a[i][j]
    a[i][j]         = a[n-j-1][i]
    a[n-j-1][i]     = a[n-i-1][n-j-1]
    a[n-i-1][n-j-1] = a[j][n-i-1]
    a[j][n-i-1]     = tmp
  end
end

pp a
 

#30 楼

 short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};

short rotated[4][4];

for (int r = 0; r < 4; ++r)
{
  for (int c = 0; c < 4; ++c)
  {
    rotated[r][c] = normal[c][3-r];
  }
}
 

简单的C ++方法，如果在大数组中会有很大的内存开销。