如何旋转一个二维数组？

Question

受雷蒙德·陈的帖子的启发，假设你有一个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^2更好的方法呢？如果矩阵是10000x10000呢？

- swilliams

---

你怎么可能只用少于n^2的步骤？所有元素都必须读取和设置，而且有n^2个元素。 - erikkallen

您的n是多少？您没有说明2D数组是否为正方形（一般情况下并非如此！例如，向量是具有一个维度为1的矩阵），但是您似乎在暗示n是宽度和高度，并且因此有n²个元素。更合理的做法是让n成为元素数量，其中n=w×h。 - niXar

以下是一种快速的方法：存储行和列索引（例如 i 和 j）。转置只需要常数时间（只需交换索引即可 :)）。您可以使用旋转进行相同的操作（玩转索引）。 - mrk

如果n^2不可行，您可以创建一个接口来访问每个元素。然后，给定(i,j)，对(i,j)应用旋转操作以访问旋转后的元素并返回其值。这可能不是最佳解决方案，但是可以使用。 - Confuse

我认为你仍然可以在小于N^2的时间内完成它。但是，需要使用更复杂的数据结构。也许是某种双向链表？ - Younes Nj

Answer 1

O(n^2)时间复杂度和O(1)空间复杂度的算法（没有任何变通和花招！）

顺时针旋转90度：

1. 转置矩阵
2. 反转每一行

逆时针旋转90度：

方法1：

1. 转置矩阵
2. 反转每一列

方法2：

1. 反转每一行
2. 转置矩阵

顺时针旋转180度：

方法1：先顺时针旋转90度，再顺时针旋转90度

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

逆时针旋转180度：

方法1：先逆时针旋转90度，再逆时针旋转90度

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

方法3：因为顺时针旋转180度和逆时针旋转180度是相同的

- dimple

---

这对我非常有帮助，一旦我了解了这个操作的“[伪]代码版本”，我就能够编写算法。谢谢！ - duma

我最喜欢的 Stack Overflow 回答之一。非常有启示性！ - user67416

如果有人感兴趣，这里有一个 JavaScript 实现 JSFiddle。 - Mr. Polywhirl

逆时针旋转90度：（1）翻转每一行；（2）转置。 Haskell代码：rotateCW = map reverse . transpose和rotateCCW = transpose . map reverse。 - Thomas Eding

旋转180度和-180度有什么区别？ - user1663023

Answer 2

我想再加一点细节。在这个答案中，关键概念被重复强调，节奏缓慢并且有意地反复。虽然提供的解决方案不是语法最紧凑的，但它旨在帮助那些想要学习矩阵旋转及其实现结果的人。

首先，什么是矩阵？对于本答案而言，矩阵只是一个宽度和高度相同的网格。请注意，矩阵的宽度和高度可以不同，但为了简单起见，本教程仅考虑宽度和高度相等的矩阵（方阵）。是的，矩阵是matrix的复数形式。

示例矩阵包括：2×2、3×3或5×5。或者更一般地说，N×N。一个2×2的矩阵将有4个正方形，因为2×2=4。一个5×5的矩阵将有25个正方形，因为5×5=25。每个正方形都称为元素或条目。我们将在下面的图表中用句点(.)表示每个元素：

2×2矩阵

. .
. .

3×3 矩阵

. . .
. . .
. . .

4x4矩阵

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

那么，旋转矩阵是什么意思呢？让我们拿一个 2×2 的矩阵，并在每个元素中放一些数字，以便观察旋转：

0 1
2 3

将此旋转90度可得：

2 0
3 1

我们实际上把整个矩阵向右旋转了一次，就像转动汽车的方向盘一样。可以将矩阵“倾斜”到右侧进行思考。我们想要编写一个Python函数，将矩阵向右旋转一次。函数签名如下：

def rotate(matrix):
    # Algorithm goes here.

矩阵将使用二维数组来定义:

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

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

matrix[row][column]

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

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

一种矩阵旋转的方法是逐层进行。但是什么是层呢？可以把洋葱作为类比，就像剥洋葱的层，每一层被移除后，我们就靠近中心了。另一个类比可以是 保卫女孩游戏 或者是俄罗斯套娃。

矩阵的宽度和高度决定该矩阵中的层数。让我们使用不同的符号来表示每个层：

一个2×2的矩阵有1层。

. .
. .

一个3×3矩阵有两层

. . .
. x .
. . .

一个4×4矩阵有两个层

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

一个5×5的矩阵有3层

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

一个6×6的矩阵有3层

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

一个7×7的矩阵有4个层

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

你可能会注意到，将矩阵的宽度和高度增加1，并不总是增加层数。通过上述矩阵并制表计算出层数和维度，我们可以看到每增加一次宽度和高度，层数增加一次：

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

然而，并不是所有的层都需要旋转。一个 1×1 的矩阵在旋转前后是相同的。无论整个矩阵有多大，中心的 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 |
+-----+--------+------------------+

给定一个 N×N 的矩阵，我们如何编程确定需要旋转的层数？如果将宽度或高度除以二并忽略余数，我们将得到以下结果。

+-----+--------+------------------+---------+
| 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 |
+-----+--------+------------------+---------+

注意到 N/2 与需要旋转的层数相对应吗？有时可旋转的层数比矩阵中总层数少一层。当最内层仅由一个元素（即1×1矩阵）构成时，会出现这种情况，因此不需要旋转它。只需忽略它。

我们在编写矩阵旋转函数时无疑需要这些信息，因此让我们现在添加它:

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

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

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

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

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

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

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

由于宽度和高度相同，这种情况将始终存在。因此，我们只需使用两个值（而不是四个）即可定义图层的列和行位置。

向第二层内移动时，列的位置为1和3。是的，你猜对了，行也是如此。重要的是要理解，当向下一层移动时，我们必须同时增加和减少行和列位置。

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

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

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)

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

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

现在我们有一个循环，提供每个层的行和列的位置。变量first和last标识第一行和列的索引位置以及最后一行和列的索引位置。回顾我们的行和列表格：

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

现在我们可以穿过一个矩阵的层。现在我们需要一种方式来在层内导航，以便我们可以移动该层中的元素。请注意，元素永远不会从一层跳到另一层，但它们确实在各自的层内移动。

旋转层中的每个元素会旋转整个层。旋转矩阵中的所有层将旋转整个矩阵。这句话非常重要，请在继续之前努力理解它。

现在，我们需要一种实际移动元素的方法，即旋转每个元素，随后是层，最终是矩阵。为简单起见，我们将恢复为一个3x3的矩阵——它具有一个可旋转的层。

0 1 2
3 4 5
6 7 8

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

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

+-----+-------+
| 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 |
+-----+-------+

由于我们的矩阵总是正方形，因此我们只需要两个变量first和last，因为行和列的索引位置相同。

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 *

我们想要将每个*与其右边的*进行交换。 因此，让我们继续打印出仅使用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

        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)

旋转角落之前的矩阵：

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

旋转角落后的矩阵：

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

太好了！我们已经成功地旋转了矩阵的每个角落。但是，我们还没有旋转每个层的中间元素。很明显，我们需要一种在层内进行迭代的方法。

问题在于，到目前为止，我们函数中唯一的循环（即我们的层循环）在每次迭代时都会移动到下一层。由于我们的矩阵只有一个可旋转的层，因此层循环在仅旋转角落后退出。让我们看一下在较大的5×5矩阵中会发生什么情况（其中两层需要旋转）。函数代码已被省略，但与上面相同：

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]

外层的角落被旋转不应该让人感到惊讶，但你可能也会注意到内层（向内）的角落也被旋转了。这是有道理的。我们编写了代码来浏览各个图层并旋转每个图层的角落。这感觉像是进步，但不幸的是我们必须退一步。在之前（外部）层的每个元素都被旋转之前，不能继续进入下一层。仅旋转角落是不够的！

深呼吸。我们需要另一个循环。嵌套循环更甚。新的嵌套循环将使用 first 和 last 变量以及偏移量在层内进行导航。我们将称此新循环为“元素循环”。元素循环将访问顶部行中的每个元素，右侧的每个元素，底部行中的每个元素和左侧上方的每个元素。

• 沿着顶行向前移动需要增加列索引。
• 向下移动右侧需要增加行索引。
• 向后沿底部移动需要减少列索引。
• 向上移动左侧需要减少行索引。

听起来很复杂，但因为我们在矩阵的所有四个侧面上增加和减少的次数是相同的，所以这变得很容易。例如：

• 将1个元素移动到顶行。
• 将1个元素向下移动右侧。
• 将1个元素向后沿底部行移动。
• 将1个元素向左方向上移动。

这意味着我们可以使用单个变量与 first 和 last 变量相结合来在层内移动。需要注意的是，沿着顶行移动和向下移动右侧都需要增加。而向后沿着底部和向上移动左侧则需要减少。

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)

现在我们只需要将顶部分配给右侧，右侧分配给底部，底部分配给左侧，左侧分配给顶部。将所有这些组合起来，我们得到：

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

考虑以下矩阵：

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

我们的rotate函数会产生以下结果：

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

- Jack

---

我最初的感觉是“哇，这是最好的解释”，但是在读了几遍后（确保我没有错过任何重要内容），我的看法变成了“我懂了，我们可以继续吗？”我仍然点赞，因为花费数小时来撰写如此精心的答案肯定不容易。 - Abhijit Sarkar

@AbhijitSarkar - 感谢您的点赞，希望这至少在某种程度上有所帮助。当然，您是正确的，我的回答太啰嗦了。然而，这是故意与绝大多数答案形成对比。正如我在回答的一开始所说的那样：“在本答案中，关键概念会被重复并且节奏缓慢，以此故意强调重复性。”如果您有任何编辑建议，可以保持清晰和必要的重复性，同时减少字数，我非常乐意听取。或者直接进行编辑 :) - Jack

TL;DR: list(zip(*reversed(your_list_of_lists))) 的作用是将一个二维列表中的元素按列重新排列并返回一个新的二维列表。 - user3064538

@Jack 提供的代码解释是我遇到过最好的之一。应该在ELI5子版中出现。非常有机和直观。 - pragun

@Jack 我必须登录以感谢你的出色答案。它非常有帮助且非常详细。 - Mr Mike

Answer 3

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

- Nick Berardi

---

可以，但使用 O(1) 的内存解决方案呢？ - AlexeyMK

你的解决方案空间复杂度为O(n^2)。需要更好的解决方案。 - Kshitij Jain

N X M矩阵呢？ - Rohit

数组中元素数量的复杂度是线性的。如果N是元素数量，则复杂度为O(N)。如果N是边长，则复杂度为O(N^2)，但这仍然是最优的。你至少需要读取每个元素一次。打印矩阵的复杂度也是相同的。 - Alejandro

进行-90度旋转：ret[i][j] = matrix[j][n - i - 1]。 - Duncan Lukkenaer

Answer 4

Python:

=>

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]语句可以将数组元素反转（请参见Extended Slices或此问题）：

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

最后，将这两者结合起来会导致旋转变换。

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

- recursive

---

我相信这段代码来源于Peter Norvig： http://www.norvig.com/python-iaq.html - Josip

你可以使用 zip(*reversed(original)) 替代 zip(*original[::-1])，以避免创建原始列表的额外副本。 - user3064538

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

- dagorym

---

在哪里？指出来，我会修复它。我已经测试过了，在奇数和偶数大小的数组上都可以正常工作。 - dagorym

这是一个优美的解决方案。如果目标明确，思维可以实现这样的壮举，从O(n2)到O(1)。 - MoveFast

它不是O(1)，它仍然是O(n^2)。 - duma

时间复杂度为 O(n^2)，空间复杂度为 O(1)。 - Neel

我真的很喜欢你划分数组的方式 :) - Duke

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

等等，一直持续到我们到边缘的中间位置

所以总的来说，这个模式就是

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

- tweaking

---

“halfway through the edge” 是什么意思？我看到很多算法循环直到N/2，而其他算法循环到N，但我看不出N/2从哪里来。 - PDN

我认为这是与《程序员面试金典》中给出的解决方案相同的解决方案。但我喜欢逐步解释。非常好和全面。 - Naphstor

@PDN 这个答案详细解释了它。 - Mathias Bynens

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

好的，我承认，在旋转时它实际上不会对原始数组进行任何修改。但是，在一个面向对象的系统中，只要对象看起来像已经被旋转了，那就无关紧要。目前，Matrix类使用对原始数组数据的引用，因此更改m1的任何值也会更改m2和m3。通过将构造函数进行小改动以创建一个新的数组并将值复制到其中即可解决这个问题。

- Skizz

---

太棒了！这是一个非常好的解决方案，我不知道为什么它没有被接受作为答案。 - martinatime

@martinatime：可能是因为它的大小是原来的五倍。 - Toad

@Toad：编写代码始终是在不同需求之间进行权衡的过程：速度、大小、成本等。 - Skizz

另一个问题是，实际上矩阵并没有旋转，但是“恰好在时间点”上进行了旋转。这对于访问少量元素非常方便，但如果该矩阵用于计算或图像处理中，将会非常糟糕。因此，说O(1)并不是很公平。 - Toad

@Toad，您是否对其进行了基准测试，以便能够对此进行可行性评估？这个解决方案可以通过删除m_matrix.GetUpperBound()调用和开关来进行优化。之后，它就可以像这样访问基本数组Matrix[width-x,height-y]，这不会比Matrix[x,y]慢得多，在我的测试中速度相同。另一个优点是，您可以处理更大的计算或图像，因为您不需要将其存储两次。它是完全可并行化的，无需交换行/元素，也无需复制内存。即使缓存也是最佳 O(N*N) 距离的 2 个循环外。 - FrankM

如果你只对旋转矩阵的几个元素感兴趣，那么这段代码就很好。它易读、易懂，而且可以检索元素。 然而，在执行完整的旋转时，这段代码会变得很慢。对于每个元素，它都有一个方法调用的开销，2D数组查找（其中包含乘法），每个set/get中都有一个switch，谁知道它对内存缓存做了什么等等。 因此，我敢打赌，去掉所有的花哨东西，使用一个非常快速的循环在原地交换元素，比这种方法更快。它会更易读吗？可能不会。 - Toad

Answer 8

虽然在原地旋转数据可能是必要的（也许是为了更新物理存储表示），但通过添加一个间接层到数组访问，例如接口，会变得更简单且可能更高效：

尽管需要在原地旋转数据（例如更新物理存储表示），但是添加一个间接层到数组访问，比如一个接口，可以使其更加简单，同时可能更加高效。

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度/270度、水平/垂直翻转和缩放。

性能需要根据特定的场景进行测量。然而，O(n^2)操作现在已经被替换为O(1)调用。这是一个虚拟方法调用，比直接数组访问要慢，因此它取决于旋转后的数组被使用的频率。如果只使用一次，那么这种方法肯定会胜出。如果旋转后在长时间运行的系统中使用，则原地旋转可能表现更好。这还取决于你是否能接受前期成本。

对于所有性能问题，都要进行度量、度量、度量！

- Drew Noakes

---

称这个解法为O(1)时间复杂度似乎有些不公平。为了解决OP提出的问题，这个方法仍需要O(n^2)的时间。而且，它也无法解决问题，因为它返回的是“转置”结果。给定的示例并不是转置的解决方案。 - Vlad the Impala

现在，如果你只想要矩阵的前三个元素，那么这是一个很好的解决方案。但问题是需要检索完全转换后的矩阵（即假设你需要所有矩阵元素）。称之为O(1)是算法分析中的信贷违约掉期方法 - 你没有解决问题，而是将问题推给了别人 :) - Ana Betts

@Paul Betts: 我理解你的观点，但正如我在评论中所写的那样，即使您实际上已经对矩阵进行了转置，如果您想读取值，仍然必须编写循环。 因此，从矩阵中读取所有值始终是O（N ^ 2），无论如何。 区别在于，如果您转置，旋转，缩放，再次缩放等，则仍然只需一次承受O（N ^ 2）的影响。 就像我说的那样，这并不总是最好的解决方案，但在许多情况下，它是适当且值得的。 OP似乎正在寻找一个神奇的解决方案，而这就是你能得到的最接近的解决方案。 - Drew Noakes

我喜欢这个答案，但我想指出一些问题。打印装饰矩阵（以及通常进行其他顺序读取）可能比对已在内存中旋转的矩阵执行相同操作要慢得多，并且这不仅仅是因为虚拟方法调用的原因。对于大型矩阵，通过"向下"而不是"横跨"读取，你将大大增加缓存错失的数量。 - Mike Daniels

@MikeDaniels：这并不是完整的故事，因为如果你一开始就用“困难的方法”在原地旋转数组，那么你当时就需要进行相同的缓存命中。只有在你在“旋转”（装饰）后以行主序顺序执行许多元素操作时，Drew的解决方案才会慢得多。 - j_random_hacker

Answer 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的文章。

- Martijn Courteaux

---

谢谢。这是这里最清晰的Java代码。问题 - 你/尼克是如何想出[w - j - 1]这部分的？看了@tweaking的答案，我可以看出你是通过归纳/解决示例来推导出这个的。只是想知道它是基于矩阵相关的某些数学原理得出的还是其他什么方法。 - Quest Monger

Answer 10

Ruby-way: .transpose.map &:reverse

- Nakilon

---

比那还要简单：array.reverse.transpose 把一个数组逆时针旋转，而 array.transpose.reverse 把它顺时针旋转。不需要用到 map。 - Giorgi Gzirishvili