如何旋转二维数组?

Inspired by Raymond Chen's post, say you have a 4x4 two dimensional array, write a function that rotates it 90 degrees. Raymond links to a solution in pseudo code, but I'd like to see some real world stuff.

灵感来自雷蒙德·陈的文章，说你有一个4x4的二维数组，写一个旋转它90度的函数。Raymond链接到一个伪代码的解决方案，但是我希望看到一些真实的世界。

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

Becomes:

就变成:

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

Update: Nick's answer is the most straightforward, but is there a way to do it better than n^2? What if the matrix was 10000x10000?

更新:尼克的回答是最简单,但有办法比n ^ 2做得更好吗?如果矩阵是10000x10000呢?

58 个解决方案

#1

Here it is in C#

这里是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) time and O(1) space algorithm ( without any workarounds and hanky-panky stuff! )

O(n ^ 2)时间和O(1)空间算法(没有任何工作区和欺诈的东西!)

Rotate by +90:

旋转+ 90:

1. Transpose
2. 转置
3. Reverse each row
4. 相反的每一行

Rotate by -90:

旋转到-90年:

Method 1 :

方法1:

1. Transpose
2. 转置
3. Reverse each column
4. 相反的每一列

Method 2 :

方法2:

1. Reverse each row
2. 相反的每一行
3. Transpose
4. 转置

Rotate by +180:

旋转+ 180:

Method 1: Rotate by +90 twice

方法1:旋转+90度。

Method 2: Reverse each row and then reverse each column (Transpose)

方法2:反转每一行，然后反转每一列(转置)

Rotate by -180:

旋转到-180年:

Method 1: Rotate by -90 twice

方法1:旋转-90度。

Method 2: Reverse each column and then reverse each row

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

Method 3: Rotate by +180 as they are same

方法3:旋转+180，因为它们是相同的。

#3

Python:

Python:

rotated = zip(*original[::-1])  # On Python 3, list(zip(*original[::-1]))

Cheap, I know.

便宜的,我知道。

And counterclockwise:

和逆时针方向:

rotated_ccw = zip(*original)[::-1]  # On Python 3, list(zip(*original))[::-1]

How this works: (Requested in comments)

如何工作:(征求意见)

zip(*original) will swap axes of 2d arrays by stacking corresponding items from lists into new lists. (The * operator tells the function to distribute the contained lists into arguments)

zip(*原始)将通过将相应的条目从列表中叠加到新的列表中来交换2d数组的轴。(*操作符告诉函数将包含的列表分配到参数中)

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

The [::-1] statement reverses array elements (please see Extended Slices).

语句反转数组元素(请参阅扩展片)。

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

Finally, combining the two will result in the rotation transformation.

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

The change in placement of [::-1] will reverse lists in different levels of the matrix.

[::-1]的位置变化将在矩阵的不同层次上反向排列。

#4

I’d like to add a little more detail. In this answer, key concepts are repeated, the pace is slow and intentionally repetitive. The solution provided here is not the most syntactically compact, it is however, intended for those who wish to learn what matrix rotation is and the resulting implementation.

我想再详细说明一下。在这个答案中，关键概念重复，节奏缓慢，故意重复。这里提供的解决方案并不是最简洁的，而是为那些希望了解矩阵旋转和结果实现的人准备的。

Firstly, what is a matrix? For the purposes of this answer, a matrix is just a grid where the width and height are the same. Note, the width and height of a matrix can be different, but for simplicity, this tutorial considers only matrices with equal width and height (square matrices). And yes, matrices is the plural of matrix.

首先，什么是矩阵?对于这个答案，矩阵只是一个网格，其中的宽度和高度是相同的。注意，矩阵的宽度和高度可以是不同的，但是为了简单起见，本教程只考虑具有相同宽度和高度的矩阵(方阵)。是的，矩阵是矩阵的复数形式。

Example matrices are: 2×2, 3×3 or 5×5. Or, more generally, N×N. A 2×2 matrix will have 4 squares because 2×2=4. A 5×5 matrix will have 25 squares because 5×5=25. Each square is called an element or entry. We’ll represent each element with a period (.) in the diagrams below:

示例矩阵:2×2,3×3或5×5。或者,更普遍的是,N×N。一个2的矩阵会有4个平方，因为2=4。5×5矩阵将有25平方,因为5×5 = 25。每个正方形称为元素或条目。我们将用一个周期(.)来表示每个元素:

2×2 matrix

2×2的矩阵

. .
. .

3×3 matrix

3×3矩阵

. . .
. . .
. . .

4×4 matrix

4×4矩阵

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

So, what does it mean to rotate a matrix? Let’s take a 2×2 matrix and put some numbers in each element so the rotation can be observed:

那么，旋转矩阵是什么意思呢?让我们来一个2×2的矩阵,把一些数字在每个元素旋转可以观察到:

0 1
2 3

Rotating this by 90 degrees gives us:

旋转90度，得到:

2 0
3 1

We literally turned the whole matrix once to the right just like turning the steering wheel of a car. It may help to think of “tipping” the matrix onto its right side. We want to write a function, in Python, that takes a matrix and rotates in once to the right. The function signature will be:

我们真的把整个矩阵变成了右边，就像转动方向盘一样。它可以帮助我们想到“把矩阵翻到右边”。我们要写一个函数，在Python里，它取一个矩阵然后向右旋转。功能签名如下:

def rotate(matrix):
    # Algorithm goes here.

The matrix will be defined using a two-dimensional array:

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

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

Therefore the first index position accesses the row. The second index position accesses the column:

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

matrix[row][column]

We’ll define a utility function to print a matrix.

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

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

One method of rotating a matrix is to do it a layer at a time. But what is a layer? Think of an onion. Just like the layers of an onion, as each layer is removed, we move towards the center. Other analogies is a Matryoshka doll or a game of pass-the-parcel.

旋转矩阵的一种方法是一次做一层。但是什么是层呢?把一个洋葱。就像洋葱的每一层，每一层都被移除，我们向中心移动。其他类似的东西是一款“大娃娃”或一款“传递包裹”的游戏。

The width and height of a matrix dictate the number of layers in that matrix. Let’s use different symbols for each layer:

矩阵的宽度和高度决定了该矩阵中的层数。让我们为每一层使用不同的符号:

A 2×2 matrix has 1 layer

一个2×2的矩阵有1层

. .
. .

A 3×3 matrix has 2 layers

3 3矩阵有2层。

. . .
. x .
. . .

A 4×4 matrix has 2 layers

4 4矩阵有2层。

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

A 5×5 matrix has 3 layers

5×5矩阵有3层

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

A 6×6 matrix has 3 layers

6 6矩阵有3层。

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

A 7×7 matrix has 4 layers

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

You may notice that incrementing the width and height of a matrix by one, does not always increase the number of layers. Taking the above matrices and tabulating the layers and dimensions, we see the number of layers increases once for every two increments of width and height:

您可能注意到，一个矩阵的宽度和高度的增加，并不总是增加层数。利用上面的矩阵和制表的层和维数，我们可以看到每增加两层的宽度和高度的层数增加一次:

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

However, not all layers need rotating. A 1×1 matrix is the same before and after rotation. The central 1×1 layer is always the same before and after rotation no matter how large the overall matrix:

然而，并不是所有的层都需要旋转。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 |
+-----+--------+------------------+

Given N×N matrix, how can we programmatically determine the number of layers we need to rotate? If we divide the width or height by two and ignore the remainder we get the following results.

给定N N矩阵，我们如何通过编程方式确定需要旋转的层数?如果我们把宽度或高度除以2，忽略剩下的，得到的结果如下。

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

Notice how N/2 matches the number of layers that need to be rotated? Sometimes the number of rotatable layers is one less the total number of layers in the matrix. This occurs when the innermost layer is formed of only one element (i.e. a 1×1 matrix) and therefore need not be rotated. It simply gets ignored.

注意N/2是如何与需要旋转的层数相匹配的?有时可旋转的层数是矩阵中各层数的一种。这种情况发生在最内层仅由一个元素(即1 1矩阵)组成，因此不需要旋转。它只是被忽略。

We will undoubtedly need this information in our function to rotate a matrix, so let’s add it now:

我们将毫无疑问地需要这个信息在我们的函数中旋转一个矩阵，所以我们现在把它加上:

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

Now we know what layers are and how to determine the number of layers that actually need rotating, how do we isolate a single layer so we can rotate it? Firstly, we inspect a matrix from the outermost layer, inwards, to the innermost layer. A 5×5 matrix has three layers in total and two layers that need rotating:

现在我们知道了什么是层，以及如何确定需要旋转的层数，我们如何分离出一个单层，这样我们就可以旋转它了?首先，我们检查一个矩阵从最外层，向内，到最里面的层。一个5×5矩阵在总有三层,两层,需要旋转:

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

Let’s look at columns first. The position of the columns defining the outermost layer, assuming we count from 0, are 0 and 4:

让我们先看看列。定义最外层的列的位置，假设我们从0算起，是0和4:

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

0 and 4 are also the positions of the rows for the outermost layer.

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

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

This will always be the case since the width and height are the same. Therefore we can define the column and row positions of a layer with just two values (rather than four).

因为宽度和高度是一样的。因此，我们可以只使用两个值(而不是4)来定义层的列和行位置。

Moving inwards to the second layer, the position of the columns are 1 and 3. And, yes, you guessed it, it’s the same for rows. It’s important to understand we had to both increment and decrement the row and column positions when moving inwards to the next layer.

向内移动到第二层，列的位置是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      |
+-----------+---------+---------+---------+

So, to inspect each layer, we want a loop with both increasing and decreasing counters that represent moving inwards, starting from the outermost layer. We’ll call this our ‘layer loop’.

因此，要检查每一层，我们需要一个既增加又减少计数器的循环，它们代表向内移动，从最外层开始。我们将其命名为“层循环”。

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)

The code above loops through the (row and column) positions of any layers that need rotating.

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

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

We now have a loop providing the positions of the rows and columns of each layer. The variables first and last identify the index position of the first and last rows and columns. Referring back to our row and column tables:

现在我们有一个循环，提供每一层的行和列的位置。变量首先确定第一个和最后一个行和列的索引位置。回到我们的行和列表:

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

So we can navigate through the layers of a matrix. Now we need a way of navigating within a layer so we can move elements around that layer. Note, elements never ‘jump’ from one layer to another, but they do move within their respective layers.

所以我们可以在矩阵的各个层中进行导航。现在我们需要一种方法在一个层中导航，这样我们就可以移动这个层的元素。注意，元素从不从一层跳到另一层，但它们确实在各自的层中移动。

Rotating each element in a layer rotates the entire layer. Rotating all layers in a matrix rotates the entire matrix. This sentence is very important, so please try your best to understand it before moving on.

在一层旋转每一个元素，旋转整个层。在矩阵中旋转所有层旋转整个矩阵。这句话很重要，所以在继续之前请尽量理解。

Now, we need a way of actually moving elements, i.e. rotate each element, and subsequently the layer, and ultimately the matrix. For simplicity, we’ll revert to a 3x3 matrix — that has one rotatable layer.

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

0 1 2
3 4 5
6 7 8

Our layer loop provides the indexes of the first and last columns, as well as first and last rows:

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

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

Because our matrices are always square, we need just two variables, first and last, since index positions are the same for rows and columns.

因为我们的矩阵总是平方的，我们只需要两个变量，第一个和最后一个，因为索引位置对于行和列是相同的。

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.

The variables first and last can easily be used to reference the four corners of a matrix. This is because the corners themselves can be defined using various permutations of first and last (with no subtraction, addition or offset of those variables):

第一个和最后一个变量可以很容易地用来引用矩阵的四个角。这是因为这些角本身可以用第一和最后的各种排列来定义(没有减法、加减或抵消这些变量):

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

For this reason, we start our rotation at the outer four corners — we’ll rotate those first. Let’s highlight them with *.

由于这个原因，我们开始在四个角上旋转——我们会先旋转它们。让我们用*来突出它们。

* 1 *
3 4 5
* 7 *

We want to swap each * with the * to the right of it. So let’s go ahead a print out our corners defined using only various permutations of first and 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)

Output should be:

输出应该是:

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

Now we could quite easily swap each of the corners from within our layer loop:

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

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)

Matrix before rotating corners:

旋转角前矩阵:

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

Matrix after rotating corners:

旋转角后矩阵:

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

Great! We have successfully rotated each corner of the matrix. But, we haven’t rotated the elements in the middle of each layer. Clearly we need a way of iterating within a layer.

太棒了!我们已经成功地旋转了矩阵的每个角。但是，我们没有在每一层中间旋转元素。显然，我们需要一种在层内迭代的方法。

The problem is, the only loop in our function so far (our layer loop), moves to the next layer on each iteration. Since our matrix has only one rotatable layer, the layer loop exits after rotating only the corners. Let’s look at what happens with a larger, 5×5 matrix (where two layers need rotating). The function code has been omitted, but it remains the same as above:

问题是，到目前为止我们的函数中唯一的循环(我们的层循环)，在每次迭代中移动到下一层。由于我们的矩阵只有一个可旋转的层，所以在旋转后，层循环就会退出。让我们看看会发生什么大,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)

The output is:

的输出是:

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

It shouldn’t be a surprise that the corners of the outermost layer have been rotated, but, you may also notice the corners of the next layer (inwards) have also been rotated. This makes sense. We’ve written code to navigate through layers and also to rotate the corners of each layer. This feels like progress, but unfortunately we must take a step back. It’s just no good moving onto the next layer until the previous (outer) layer has been fully rotated. That is, until each element in the layer has been rotated. Rotating only the corners won’t do!

最外层的角已经旋转，这并不奇怪，但是，你也可以注意到下一层(内部)的角也被旋转了。这是有意义的。我们编写了代码来导航各个层，也可以旋转每个层的各个角落。这是一种进步，但不幸的是，我们必须后退一步。在上一层(外层)完全旋转之前，移动到下一层是不好的。也就是说，直到层中的每个元素都被旋转。转弯抹角是不行的!

Take a deep breath. We need another loop. A nested loop no less. The new, nested loop, will use the first and last variables, plus an offset to navigate within a layer. We’ll call this new loop our ‘element loop’. The element loop will visit each element along the top row, each element down the right side, each element along the bottom row and each element up the left side.

做个深呼吸。我们需要另一个循环。一个嵌套循环。新的嵌套循环将使用第一个和最后一个变量，以及在一个层中导航的偏移量。我们将这个新循环称为“元素循环”。元素循环将访问沿顶部行的每个元素，每个元素沿着右侧，每个元素沿着底部行和每个元素在左边。

• Moving forwards along the top row requires the column index to be incremented.
• 沿着顶行向前移动需要增加列索引。
• Moving down the right side requires the row index to be incremented.
• 向右移动需要增加行索引。
• Moving backwards along the bottom requires the column index to be decremented.
• 沿着底部向后移动需要减少列索引。
• Moving up the left side requires the row index to be decremented.
• 在左侧向上移动需要将行索引递减。

This sounds complex, but it’s made easy because the number of times we increment and decrement to achieve the above remains the same along all four sides of the matrix. For example:

这听起来很复杂，但这很容易，因为在矩阵的所有四个方面，我们递增和递减的次数都是相同的。例如:

• Move 1 element across the top row.
• 将一个元素移动到顶部一行。
• Move 1 element down the right side.
• 右移1个元素。
• Move 1 element backwards along the bottom row.
• 沿着底部一行向后移动1个元素。
• Move 1 element up the left side.
• 左移1个元素。

This means we can use a single variable in combination with the first and last variables to move within a layer. It may help to note that moving across the top row and down the right side both require incrementing. While moving backwards along the bottom and up the left side both require decrementing.

这意味着我们可以使用单个变量与第一个变量和最后一个变量在一个层中移动。它可以帮助我们注意到，在最上面一行和右下方移动都需要递增。当沿着底部向后移动时，左边和右边都需要递减。

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_element = (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)

Now we simply need to assign the top to the right side, right side to the bottom, bottom to the left side, and left side to the top. Putting this all together we get:

现在我们只需要把上面的部分分配到右边，右边到底部，从底部到左边，然后从左边到顶部。把这些放在一起，我们得到:

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

Given the matrix:

鉴于矩阵:

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

Our rotate function results in:

我们的旋转函数的结果是:

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

#5

Here is one that does the rotation in place instead of using a completely new array to hold the result. I've left off initialization of the array and printing it out. This only works for square arrays but they can be of any size. Memory overhead is equal to the size of one element of the array so you can do the rotation of as large an array as you want.

这里是一个旋转的地方，而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化并将其打印出来。这只适用于正方形数组，但它们可以是任意大小。内存开销等于数组的一个元素的大小，这样就可以根据需要进行任意大数组的旋转。

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

There are tons of good code here but I just want to show what's going on geometrically so you can understand the code logic a little better. Here is how I would approach this.

这里有很多很好的代码，但我只是想展示一下几何上发生了什么，这样你就能更好地理解代码逻辑了。下面是我的方法。

first of all, do not confuse this with transposition which is very easy..

首先，不要把这个和转位混淆起来，这很容易。

the basica idea is to treat it as layers and we rotate one layer at a time..

basica的想法是把它当作层，我们一次旋转一层。

say we have a 4x4

假设我们有4x4。

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

after we rotate it clockwise by 90 we get

在我们顺时针旋转90后得到。

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

so let's decompose this, first we rotate the 4 corners essentially

让我们分解这个，首先我们要旋转四个角。

1           4


13          16

then we rotate the following diamond which is sort of askew

然后我们旋转下面的菱形，这是一种歪斜。

    2
            8
9       
        15

and then the 2nd skewed diamond

然后是第二颗倾斜的钻石。

        3
5           
            12
    14

so that takes care of the outer edge so essentially we do that one shell at a time until

这就得到了外边缘所以我们每次只做一个壳。

finally the middle square (or if it's odd just the final element which does not move)

最后是中间的正方形(或者如果它是奇数，就是最后一个不动的元素)

6   7
10  11

so now let's figure out the indices of each layer, assume we always work with the outermost layer, we are doing

现在我们来算出每一层的指数，假设我们总是在最外层，我们在做。

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

so on and so on until we are halfway through the edge

等等，直到我们走到一半。

so in general the pattern is

一般来说，模式是。

[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

As I said in my previous post, here's some code in C# that implements an O(1) matrix rotation for any size matrix. For brevity and readability there's no error checking or range checking. The code:

正如我在之前的文章中说过的，这里有一些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;
}

OK, I'll put my hand up, it doesn't actually do any modifications to the original array when rotating. But, in an OO system that doesn't matter as long as the object looks like it's been rotated to the clients of the class. At the moment, the Matrix class uses references to the original array data so changing any value of m1 will also change m2 and m3. A small change to the constructor to create a new array and copy the values to it will sort that out.

好的，我把我的手举起来，它在旋转时不会对原始数组做任何修改。但是，在一个面向对象的系统中，只要对象看起来像被旋转到类的客户端，它就不重要了。此时，矩阵类使用对原始数组数据的引用，因此改变m1的任何值也会改变m2和m3。对构造函数进行一个小的更改，以创建一个新的数组并将值复制到它将会解决这个问题。

#8

Whilst rotating the data in place might be necessary (perhaps to update the physically stored representation), it becomes simpler and possibly more performant to add a layer of indirection onto the array access, perhaps an interface:

在适当的地方旋转数据可能是必要的(也许是为了更新物理存储的表示)，它变得更简单，也可能更有性能，在数组访问中添加一个间接层，可能是一个接口:

interface IReadableMatrix
{
    int GetValue(int x, int y);
}

If your Matrix already implements this interface, then it can be rotated via a decorator class like this:

如果您的矩阵已经实现了这个接口，那么它可以通过这样的decorator类进行旋转:

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

Rotating +90/-90/180 degrees, flipping horizontally/vertically and scaling can all be achieved in this fashion as well.

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

性能需要在您的特定场景中进行度量。但是O(n ^ 2)操作已经被替换为一个O(1)的电话。这是一个虚拟的方法调用，它比直接数组访问慢，所以这取决于旋转后的阵列频繁使用的频率。如果使用一次，那么这种方法肯定会赢。如果它被旋转，然后在一个长时间运行的系统中使用几天，那么就地旋转可能会更好。这还取决于你是否能接受预付的费用。

As with all performance issues, measure, measure, measure!

和所有的性能问题一样，测量，测量，测量!

#9

This a better version of it in Java: I've made it for a matrix with a different width and height

这是Java的一个更好的版本:我已经为一个具有不同宽度和高度的矩阵制作了它。

• h is here the height of the matrix after rotating
• h是旋转后矩阵的高度。
• w is here the width of the matrix after rotating
• 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;
}

This code is based on Nick Berardi's post.

这段代码基于Nick Berardi的帖子。

#10

Ruby-way: .transpose.map &:reverse

ruby方式:.transpose。地图&:反向

#11

There are a lot of answers already, and I found two claiming O(1) time complexity. The real O(1) algorithm is to leave the array storage untouched, and change how you index its elements. The goal here is that it does not consume additional memory, nor does it require additional time to iterate the data.

已经有很多的答案了，我发现了两个声称的时间复杂度。真正的O(1)算法是保持数组存储不变，并更改如何索引其元素。这里的目标是，它不消耗额外的内存，也不需要额外的时间来迭代数据。

Rotations of 90, -90 and 180 degrees are simple transformations which can be performed as long as you know how many rows and columns are in your 2D array; To rotate any vector by 90 degrees, swap the axes and negate the Y axis. For -90 degree, swap the axes and negate the X axis. For 180 degrees, negate both axes without swapping.

90，-90和180度的旋转是简单的变换，只要你知道二维数组中有多少行和列，就可以执行。要将任意向量旋转90度，交换坐标轴并否定Y轴。对于-90度，交换坐标轴，并否定X轴。180度，不交换两个轴。

Further transformations are possible, such as mirroring horizontally and/or vertically by negating the axes independently.

进一步的转换是可能的，例如水平和/或垂直地通过对坐标轴进行独立镜像。

This can be done through e.g. an accessor method. The examples below are JavaScript functions, but the concepts apply equally to all languages.

这可以通过一个访问器方法来完成。下面的示例是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.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr.length; i++) {
  for (var j = 0; j < newarr[0].length; j++) {
    newarr[i][j] = 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.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr.length; i++) {
  for (var j = 0; j < newarr[0].length; j++) {
    newarr[i][j] = 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[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] = getArray2d180(arr, i, j);
  }
}
console.log(newarr);

This code assumes an array of nested arrays, where each inner array is a row.

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

The method allows you to read (or write) elements (even in random order) as if the array has been rotated or transformed. Now just pick the right function to call, probably by reference, and away you go!

该方法允许您读取(或写入)元素(甚至是随机顺序)，就像数组已经被旋转或转换一样。现在选择正确的函数调用，可能是引用，然后离开!

The concept can be extended to apply transformations additively (and non-destructively) through the accessor methods. Including arbitrary angle rotations and scaling.

可以扩展这个概念，通过访问器方法添加(和非破坏性的)转换。包括任意角度旋转和缩放。

#12

A couple of people have already put up examples which involve making a new array.

有几个人已经举了一些例子，涉及到制作一个新的数组。

A few other things to consider:

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

(a) Instead of actually moving the data, simply traverse the "rotated" array differently.

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

(b) Doing the rotation in-place can be a little trickier. You'll need a bit of scratch place (probably roughly equal to one row or column in size). There's an ancient ACM paper about doing in-place transposes (http://doi.acm.org/10.1145/355719.355729), but their example code is nasty goto-laden FORTRAN.

(b)就地旋转可能有点棘手。您将需要一些scratch的地方(可能大致相当于一行或一列的大小)。有一种古老的ACM文件，是关于如何进行本地转置的(http://doi.acm.org/10.1145/355719.355729)，但是他们的示例代码是令人讨厌的goto-laden FORTRAN。

Addendum:

附录:

http://doi.acm.org/10.1145/355611.355612 is another, supposedly superior, in-place transpose algorithm.

http://doi.acm.org/10.1145/355611.355612是另一种被认为是优越的置位转置算法。

#13

Nick's answer would work for an NxM array too with only a small modification (as opposed to an NxN).

尼克的回答也适用于一个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];

One way to think about this is that you have moved the center of the axis (0,0) from the top left corner to the top right corner. You're simply transposing from one to the other.

一种思考方法是，从左上角到右上角，移动了轴的中心(0,0)。你只是从一个转到另一个。

#14

Here's my Ruby version (note the values aren't displayed the same, but it still rotates as described).

这是我的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))

The output:

输出:

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

#15

Time - O(N), Space - O(1)

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

#16

here's a in-space rotate method, by java, only for square. for non-square 2d array, you will have to create new array anyway.

这是一个空间内旋转的方法，由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;
            }
        }
    }
}

code to rotate any size 2d array by creating new array:

通过创建新数组来旋转任意大小的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

Implementation of dimple's +90 pseudocode (e.g. transpose then reverse each row) in JavaScript:

在JavaScript中实现dimple的+90伪代码(例如转置，然后反转每一行):

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

You can do this in 3 easy steps:

你可以用3个简单的步骤来做:

1)Suppose we have a matrix

假设我们有一个矩阵。

   1 2 3
   4 5 6
   7 8 9

2)Take the transpose of the matrix

2)取矩阵的转置。

   1 4 7
   2 5 8
   3 6 9

3)Interchange rows to get rotated matrix

3)交换行以得到旋转矩阵。

   3 6 9
   2 5 8
   1 4 7

Java source code for this:

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

Output:

输出:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 

#19

PHP:

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

#20

This is my implementation, in C, O(1) memory complexity, in place rotation, 90 degrees clockwise:

这是我的实现，在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;
        }
    }
}

#21

Here is the Java version:

下面是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;
        }
    }
}

the method first rotate the mostouter layer, then move to the inner layer squentially.

该方法首先旋转最外层，然后按顺序移动到内层。

#22

From a linear point of view, consider the matrices:

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

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

Now take A transpose

现在转置

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

And consider the action of A' on B, or B on A'.
Respectively:

并考虑A' on B，或B on A'的动作。分别为:

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

This is expandable for any n x n matrix. And applying this concept quickly in code:

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

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

#23

C# code to rotate [n,m] 2D arrays 90 deg right

c#代码旋转[n,m] 2D数组90 deg对。

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

Result:

结果:

    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

#24

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

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

X is the size of the array the graphic is in.

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

#25

#transpose is a standard method of Ruby's Array class, thus:

#转置是Ruby数组类的标准方法，因此:

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

The implementation is an n^2 transposition function written in C. You can see it here: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose by choosing "click to toggle source" beside "transpose".

实现是一个n ^ 2换位函数写在c。在这里你可以看到:http://www.ruby-doc.org/core-1.9.3/Array.html method-i-transpose通过选择“点击切换源”旁边的“转置”。

I recall better than O(n^2) solutions, but only for specially constructed matrices (such as sparse matrices)

我记得比O(n ^ 2)的解决方案,但仅限于特殊构造的矩阵(如稀疏矩阵)

#26

C code for matrix rotation 90 degree clockwise IN PLACE for any M*N matrix

C代码为矩阵旋转90度，适用于任何M*N矩阵。

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

here is my In Place implementation in C

这是我在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

Here is my attempt for matrix 90 deg rotation which is a 2 step solution in C. First transpose the matrix in place and then swap the cols.

这是我对矩阵90 deg旋转的尝试，这是c的2步解，先把矩阵转置，然后交换高斯。

#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: Aw, man. I had been hanging onto this as a good "I'm bored, what can I ponder" puzzle. I came up with my in-place transposition code, but got here to find yours pretty much identical to mine...ah, well. Here it is in Ruby.

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

Simple C++ method, tho there would be a big memory overhead in a big array.

简单的c++方法，在一个大的数组中会有一个很大的内存开销。