关于算法：如何旋转二维数组？

How do you rotate a two dimensional array?

受RaymondChen文章的启发，假设你有一个4x4二维数组，写一个旋转90度的函数。Raymond用伪代码链接到一个解决方案，但我想看看现实世界中的一些东西。

1
2
3
4

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

变成：

1
2
3
4

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

更新：尼克的回答是最直接的，但是有没有比N^2更好的方法？如果矩阵是10000x1000呢？

O(N ^ 2)的时间和O(1)算法的空间(没有任何workarounds和hanky - panky东西！)

前言：rotate + 90

transpose

反对方行

前言：rotate 90

方法一：

transpose

反对方柱

方法2：

反对方行

transpose

前言：rotate + 180

方法：由一个rotate + 90次

方法2：反对方，然后反每一列(Row transpose)

前言：rotate - 180

方法1：rotate由90次

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

方法三：由+ 180 rotate作为他们是相同的

我想再加一点细节。在这个答案中，关键概念是重复的，节奏缓慢，有意重复。然而，这里提供的解决方案在语法上并不是最紧凑的，它是为那些希望了解矩阵旋转是什么以及结果实现的人设计的。好的。

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

示例矩阵为：2×2、3×3或5×5。或者，更一般地说，n×n。一个2×2矩阵将有4个正方形，因为2×2=4。一个5×5的矩阵将有25个正方形，因为5×5=25。每个方块都被称为元素或入口。我们将在下图中用句点(.表示每个元素：好的。

2×2矩阵好的。

1
2

. .
. .

3×3矩阵好的。

1
2
3

. . .
. . .
. . .

4×4矩阵好的。2

那么，旋转矩阵意味着什么呢？让我们取一个2×2的矩阵，在每个元素中加上一些数字，这样就可以观察到旋转：好的。

1
2

0 1
2 3

旋转90度可以得到：好的。

1
2

2 0
3 1

我们真的把整个矩阵向右转了一次，就像转动汽车的方向盘一样。这可能有助于思考"倾斜"矩阵的右边。我们想用python编写一个函数，它接受一个矩阵并向右旋转一次。函数签名将是：好的。

1 2	def rotate(matrix): # Algorithm goes here.

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

1
2
3
4

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

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

1	matrix[row][column]

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

1
2
3

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

旋转矩阵的一种方法是一次旋转一层。但是什么是层呢？想想洋葱。就像洋葱的每一层，当每一层被移除时，我们都会向中心移动。其他的类比是一个套娃或一个传递包裹的游戏。好的。

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

2×2矩阵有1层好的。

1
2

. .
. .

3×3矩阵有两层好的。

1
2
3

. . .
. x .
. . .

4×4矩阵有两层好的。

1
2
3
4

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

5×5矩阵有3层好的。

1
2
3
4
5

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

6×6矩阵有3层好的。

1
2
3
4
5
6

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

7×7矩阵有4层好的。

1
2
3
4
5
6
7

. . . . . . .
. 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
2
3
4
5
6
7
8
9
10
11

+-----+--------+
| 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层在旋转前后始终相同，无论整体矩阵有多大：好的。

1
2
3
4
5
6
7
8
9
10
11

+-----+--------+------------------+
| 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矩阵，我们如何以编程方式确定需要旋转的层数？如果我们将宽度或高度除以2，忽略余数，我们得到以下结果。好的。2

注意，N/2如何匹配需要旋转的层数？有时，可旋转层的数量比矩阵中的总层数少一个。当最内层仅由一个元素(即1×1矩阵)构成，因此不需要旋转时，就会发生这种情况。它只是被忽略了。好的。

毫无疑问，我们在函数中需要这些信息来旋转矩阵，现在让我们添加它：好的。

1
2
3
4

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

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

1
2
3
4
5

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

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

1
2
3
4
5
6
7
8
9

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

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

1
2
3
4
5
6
7
8
9

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

因为宽度和高度是相同的，所以情况总是如此。因此，我们可以定义只有两个值(而不是四个)的层的列和行位置。好的。

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

1
2
3
4
5
6
7

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

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

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

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)

上面的代码循环通过需要旋转的任何层的(行和列)位置。好的。

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

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

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

+--------+-----------+
| 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矩阵-它有一个可旋转层。好的。

1
2
3

0 1 2
3 4 5
6 7 8

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

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

+-----+-------+
| 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，因为行和列的索引位置是相同的。好的。2

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

1
2
3
4
5
6
7
8

因为这个原因，我们从外面的四个角开始旋转，我们先旋转它们。让我们用*来突出它们。好的。

1
2
3

* 1 *
3 4 5
* 7 *

我们想把每个*和*互换到它的右边。因此，让我们继续打印我们的角点，只使用first和last的各种排列：好的。

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

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)

输出应为：好的。

1
2
3
4

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 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
25
26
27

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)

转角前矩阵：好的。

1
2
3

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

转角后的矩阵：好的。

1
2
3

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

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

问题是，到目前为止，函数中唯一的循环(我们的层循环)在每次迭代中移动到下一层。因为我们的矩阵只有一个可旋转层，所以层循环在只旋转角之后退出。让我们看一个更大的5×5矩阵会发生什么(两个层需要旋转)。功能代码已被省略，但仍与上面相同：好的。

1
2
3
4
5
6
7
8
9
10
11

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)

输出是：好的。

1
2
3
4
5

[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个元素向上移动到左侧。

这意味着我们可以将单个变量与first和last变量结合使用，在一个层中移动。需要注意的是，在最上面一行和最右边移动都需要递增。沿底部和左侧向后移动时，两者都需要减量。好的。

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
26
27
28

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)

现在我们只需要将顶部分配给右侧，右侧分配给底部，底部分配给左侧，左侧分配给顶部。把这些放在一起，我们得到：好的。

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

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

给定矩阵：好的。2

我们的rotate功能导致：好的。

1
2
3

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

好啊。

这是C的#

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

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

Python：

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

廉价的，我知道。

和counterclockwise：

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

如何：(设计了这个作品在评论)

zip(*original)威尔swap axes的二维arrays由从对应的stacking items列出成新的列表。(《*告诉操作员的功能distribute列出其中的成大的支持)

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

该项声明[::-1]reverses阵列元素(请参见扩展slices)。

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

最后，将导致在两combining旋转转型。

的位置的变化在[::-1]将列出在不同水平的反矩阵。

这是一个在适当位置执行旋转的方法，而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化并将其打印出来。这只适用于方形阵列，但它们可以是任何大小。内存开销等于数组中一个元素的大小，因此可以根据需要旋转任意大的数组。

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

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

这里有很多好的代码，但我只是想从几何角度展示正在发生的事情，这样您就可以更好地理解代码逻辑。下面是我将如何处理这个问题。

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

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

假设我们有4x4

1
2
3
4

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

当我们顺时针旋转90度后，我们得到

1
2
3
4

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

让我们来分解这个，首先我们基本上旋转4个角

然后我们旋转下面的钻石，它有点歪斜

1
2
3
4

2
8
9
15

然后是第二颗歪斜的钻石

1
2
3
4

3
5
12
14

所以这要考虑到外缘，所以我们一次只做一个壳，直到

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

1
2

6 7
10 11

现在让我们计算出每一层的索引，假设我们总是使用最外层，我们正在这样做

1
2
3

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

如此等等直到我们走到边缘的一半

一般来说，模式是

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

正如我在上一篇文章中所说，这里有一些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。对构造函数进行一个小的更改，以创建一个新数组并将值复制到该数组中，这将解决这个问题。

虽然就地旋转数据可能是必要的(可能是为了更新物理存储的表示)，但向阵列访问(可能是接口)添加一个间接层会变得更简单，性能也可能更高：

1
2
3
4

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

如果您的Matrix已经实现了这个接口，那么它可以通过如下的decorator类进行旋转：

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

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)调用。这是一个虚拟方法调用，比直接数组访问慢，因此它取决于旋转后使用旋转数组的频率。如果使用过一次，那么这种方法肯定会赢。如果旋转，然后在长时间运行的系统中使用几天，那么就地旋转可能会更好。这还取决于你是否能接受预付费用。

和所有性能问题一样，测量、测量、测量！

它在这一个更好的Java版的：我已经把它，对于一个矩阵与一个不同的width和高度

他是这里的高度后rotating矩阵的研究
W是这里的width后rotating矩阵的研究

与nbsp；

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
26
27
28

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

本代码是基于berardi Nick的后。

方法：.transpose.map &:reverse红宝石-

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

90度、90度和180度的旋转是简单的转换，只要知道二维数组中有多少行和列，就可以执行转换；要将任何向量旋转90度，请交换轴并使Y轴为负。对于-90度，交换轴并使X轴为负。180度时，不交换两个轴。

进一步的转换是可能的，例如通过单独否定轴来水平和/或垂直镜像。

这可以通过访问器方法来实现。下面的例子是JavaScript函数，但是这些概念同样适用于所有语言。

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

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

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
26

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

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

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

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

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

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

一些人已经举了一些例子，其中包括创建一个新的数组。

需要考虑的其他一些事项：

(a)不需要实际移动数据，只需以不同的方式遍历"旋转"数组即可。

(b)在适当的位置进行旋转可能有点棘手。您将需要一些临时位置(大概相当于一行或一列的大小)。有一篇关于就地转置的古老ACM论文(http://doi.acm.org/10.1145/355719.355729)，但是他们的示例代码是讨厌的Goto-Laden Fortran。

附录：

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

Nick的答案也适用于NXM阵列，只需稍作修改(与NXN相反)。

1
2
3
4
5
6
7
8

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)从左上角移动到右上角。你只是简单地从一个调换到另一个。

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

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

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

这是我的Ruby版本(请注意，这些值显示的不一样，但它仍按描述旋转)。

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
26
27
28
29
30

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

输出：

这是一个在空间rotate方法，由Java，只为广场。对于非广场的二维阵列，你将要创建新阵列吧。

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

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

大尺寸rotate代码由任何二维阵列创建新阵列：

1
2
3
4
5
6
7
8
9
10
11

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

您可以通过3个简单步骤来完成此操作：

1)假设我们有一个矩阵

1
2
3

1 2 3
4 5 6
7 8 9

2)取矩阵的转置

1
2
3

1 4 7
2 5 8
3 6 9

3)交换行以获得旋转矩阵

1
2
3

3 6 9
2 5 8
1 4 7

Java源代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

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

1 2 3
4 5 6
7 8 9

3 6 9
2 5 8
1 4 7

实施的dimple OH + 90 pseudocode(例如transpose在JavaScript然后反向每Row)：

1
2
3
4
5
6
7
8
9

这是我的实施，C，O(1)内存的复杂性，在顺时针旋转90度的地方，：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#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
");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d", m[i][j]);
}
printf("
");
}
printf("
");
}

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

PHP：

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

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

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

1
2
3

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

现在换位

1
2
3

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

并考虑a'对b，或b对a'的作用。分别：

1
2
3

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

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

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
26
27
28
29
30
31
32

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

这里是Java的版本：

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

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

该方法的第一rotate mostouter层，然后移动到的内在的squentially层。

C代码将[N，M]二维数组向右旋转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();
}
}
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

# transpose是一个标准的Ruby的阵列方法的类，因此：

1
2
3
4
5

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

的实施是一个N ^ 2 transposition函数写在这里：你可以看到它。 HTTP:/ / www.ruby-doc.org /核心/方法- 1.9.3 array.html # I transpose 选择"由大toggle点击"源"beside transpose"。

我记得比O(N ^ 2)的解决方案，但只为specially建成矩阵(如sparse矩阵)

这里是我的attempt为90随便啦，窦或这是一个旋转矩阵的两个步骤的解决方案在第一transpose C.在地方swap然后的矩阵的列。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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

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

这里是我的在地方的实施C

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

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

C代码为顺时针旋转90度的矩阵在任何地方为M×N矩阵

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
26

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

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

X是的大小是在graphic阵列的研究。

1
2
3
4
5
6
7
8
9

private static int[][] rotate(int[][] matrix, int n) {
int[][] rotated = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotated[i][j] = matrix[n-j-1][i];
}
}
return rotated;
}

运行时o(n^2)和内存o(1)的nxn矩阵的javascript解决方案

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

1
2
3
4
5
6
7
8
9
10
11

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 + +的方法，大有将是一个舒适的overhead内存在一个大的阵列。

很好的答案，但是对于那些正在寻找干巴巴巴的javascript代码的人来说，无论是+90度还是-90度：

// Input: 1 2 3
// 4 5 6
// 7 8 9

// Transpose:
// 1 4 7
// 2 5 8
// 3 6 9

// Output:
// +90 Degree:
// 7 4 1
// 8 5 2
// 9 6 3

// -90 Degree:
// 3 6 9
// 2 5 8
// 1 4 7

// Rotate +90
function rotate90(matrix) {

matrix = transpose(matrix);
matrix.map(function(array) {
array.reverse();
});

return matrix;
}

// Rotate -90
function counterRotate90(matrix) {
var result = createEmptyMatrix(matrix.length);
matrix = transpose(matrix);
var counter = 0;

for (var i = matrix.length - 1; i >= 0; i--) {
result[counter] = matrix[i];
counter++;
}

return result;
}

// Create empty matrix
function createEmptyMatrix(len) {
var result = new Array();
for (var i = 0; i < len; i++) {
result.push([]);
}
return result;
}

// Transpose the matrix
function transpose(matrix) {
// make empty array
var len = matrix.length;
var result = createEmptyMatrix(len);

for (var i = 0; i < matrix.length; i++) {
for (var j = 0; j < matrix[i].length; j++) {
var temp = matrix[i][j];
result[j][i] = temp;
}
}
return result;
}

// Test Cases
var array1 = [
[1, 2],
[3, 4]
];
var array2 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
var array3 = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];

// +90 degress Rotation Tests

var test1 = rotate90(array1);
var test2 = rotate90(array2);
var test3 = rotate90(array3);
console.log(test1);
console.log(test2);
console.log(test3);

// -90 degress Rotation Tests
var test1 = counterRotate90(array1);
var test2 = counterRotate90(array2);
var test3 = counterRotate90(array3);
console.log(test1);
console.log(test2);
console.log(test3);

@达戈里姆：哦，伙计。我一直认为这是一个很好的"我很无聊，我能思考什么"难题。我想出了我的原地换位代码，但到了这里发现你的和我的几乎一样…啊，好吧。这是红宝石的。

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

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

用于顺时针和逆时针的PHP解决方案

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

$aMatrix = array(
array( 1, 2, 3 ),
array( 4, 5, 6 ),
array( 7, 8, 9 )
);

function CounterClockwise( $aMatrix )
{
$iCount = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $iCount - $x - 1 ][ $y ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}

function Clockwise( $aMatrix )
{
$iCount = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $x ][ $iCount - $y - 1 ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}

function printMatrix( $aMatrix )
{
$iCount = count( $aMatrix );
for( $x = 0; $x < $iCount; ++$x )
{
for( $y = 0; $y < $iCount; ++$y )
{
echo $aMatrix[ $x ][ $y ];
echo"";
}
echo"
";
}
}
printMatrix( $aMatrix );
echo"
";
$aNewMatrix = CounterClockwise( $aMatrix );
printMatrix( $aNewMatrix );
echo"
";
$aNewMatrix = Clockwise( $aMatrix );
printMatrix( $aNewMatrix );

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>
#include <iomanip>

using namespace std;
const int SIZE=3;
void print(int a[][SIZE],int);
void rotate(int a[][SIZE],int);

void main()
{
int a[SIZE][SIZE]={{11,22,33},{44,55,66},{77,88,99}};
cout<<"the array befor rotate
";

print(a,SIZE);
rotate( a,SIZE);
cout<<"the array after rotate
";
print(a,SIZE);
cout<<endl;

}

void print(int a[][SIZE],int SIZE)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
cout<<a[i][j]<<setw(4);
}

void rotate(int a[][SIZE],int SIZE)
{
int temp[3][3],i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE/2.5;j++)
{
temp[i][j]= a[i][j];
a[i][j]= a[j][SIZE-i-1] ;
a[j][SIZE-i-1] =temp[i][j];

}
}

所有当前的解决方案是O(N ^ 2)作为空间overhead从头开始(这excludes那些骗子filthy哦！)这里是一个解决方案。与O(1)的矩阵的内存使用，rotating在90 degress正确的地方。这sucker screw extensibility，运行快速。

1
2
3
4
5
6
7
8
9
10
11

#include
#include <cstddef>

// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
for(size_t i = 0; i < N; ++i)
for(size_t j = 0; j <= (N-i); ++j)
std::swap(matrix[i][j], matrix[j][i]);
}

disclaimer测试：我不在这。让我们一起玩游戏-错误！

基于Communitywiki算法和这个对数组转置的答案，这里有一个Swift4版本，可以将一些二维数组逆时针旋转90度。这假设matrix是一个二维数组：

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

func rotate(matrix: [[Int]]) -> [[Int]] {
let transposedPoints = transpose(input: matrix)
let rotatedPoints = transposedPoints.map{ Array($0.reversed()) }
return rotatedPoints
}

fileprivate func transpose<T>(input: [[T]]) -> [[T]] {
if input.isEmpty { return [[T]]() }
let count = input[0].count
var out = [[T]](repeating: [T](), count: count)
for outer in input {
for (index, inner) in outer.enumerated() {
out[index].append(inner)
}
}

return out
}

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

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
26
27
28
29
30
31
32

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

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

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

我的旋转版本：

1
2
3
4
5
6
7
8
9
10
11
12

void rotate_matrix(int *matrix, int size)
{

int result[size*size];

for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
result[(size - 1 - i) + j*size] = matrix[i*size+j];

for (int i = 0; i < size*size; ++i)
matrix[i] = result[i];
}

在它中，我们将最后一列更改为第一行，如此进一步。这可能不是最佳的，但要理解清楚。

基于大量其他答案，我在C中提出了这个问题：

/// <param name="rotation">The number of rotations (if negative, the <see cref="Matrix{TValue}"/> is rotated counterclockwise;
/// otherwise, it's rotated clockwise). A single (positive) rotation is equivalent to 90° or -270°; a single (negative) rotation is
/// equivalent to -90° or 270°. Matrices may be rotated by 90°, 180°, or 270° only (or multiples thereof).</param>
/// <returns></returns>
public Matrix<TValue> Rotate(int rotation)
{
var result = default(Matrix<TValue>);

//This normalizes the requested rotation (for instance, if 10 is specified, the rotation is actually just +-2 or +-180°, but all
//correspond to the same rotation).
var d = rotation.ToDouble() / 4d;
d = d - (int)d;

var degree = (d - 1d) * 4d;

//This gets the type of rotation to make; there are a total of four unique rotations possible (0°, 90°, 180°, and 270°).
//Each correspond to 0, 1, 2, and 3, respectively (or 0, -1, -2, and -3, if in the other direction). Since
//1 is equivalent to -3 and so forth, we combine both cases into one.
switch (degree)
{
case -3:
case +1:
degree = 3;
break;
case -2:
case +2:
degree = 2;
break;
case -1:
case +3:
degree = 1;
break;
case -4:
case 0:
case +4:
degree = 0;
break;
}
switch (degree)
{
//The rotation is 0, +-180°
case 0:
case 2:
result = new TValue[Rows, Columns];
break;
//The rotation is +-90°
case 1:
case 3:
result = new TValue[Columns, Rows];
break;
}

for (uint i = 0; i < Columns; ++i)
{
for (uint j = 0; j < Rows; ++j)
{
switch (degree)
{
//If rotation is 0°
case 0:
result._values[j][i] = _values[j][i];
break;
//If rotation is -90°
case 1:
//Transpose, then reverse each column OR reverse each row, then transpose
result._values[i][j] = _values[j][Columns - i - 1];
break;
//If rotation is +-180°
case 2:
//Reverse each column, then reverse each row
result._values[(Rows - 1) - j][(Columns - 1) - i] = _values[j][i];
break;
//If rotation is +90°
case 3:
//Transpose, then reverse each row
result._values[i][j] = _values[Rows - j - 1][i];
break;
}
}
}
return result;
}

其中，_values对应于由Matrix定义的私有二维数组(以[][]的形式)。result = new TValue[Columns, Rows]可以通过隐式运算符重载实现，并将二维数组转换为Matrix。Columns和Rows这两个属性是获取当前实例的列和行数的公共属性：

1
2
3
4
5

public uint Columns
=> (uint)_values[0].Length;

public uint Rows
=> (uint)_values.Length;

当然，假设您更喜欢使用无符号索引；-)

所有这些都允许您指定应该旋转多少次，以及应该向左旋转(如果小于零)还是向右旋转(如果大于零)。您可以改进它以检查实际度数的旋转情况，但是如果该值不是90的倍数，那么您需要抛出一个异常。使用该输入，您可以相应地更改方法：

由于用double表示的度数比int表示的更准确，但矩阵只能以90的倍数旋转，因此使参数与其他可以用所用数据结构精确表示的参数相对应要直观得多。int是完美的，因为它可以告诉你旋转多少次到某个单位(90)以及方向。double可能也能很好地告诉您，但它还包括不受此操作支持的值(本质上是反直觉的)。

矩阵转置和旋转的C代码(+/-90，+/-180)

支持正方形和非正方形矩阵，具有就地和复制功能
支持具有逻辑行/列的二维数组和一维指针
单元测试；使用示例见测试
测试GCC-标准=C90-墙壁-踏板，MSVC17

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359

#include <stdlib.h>
#include <memory.h>
#include

/*
Matrix transpose & rotate (+/-90, +/-180)
Supports both 2D arrays and 1D pointers with logical rows/cols
Supports square and non-square matrices, has in-place and copy features
See tests for examples of usage
tested gcc -std=c90 -Wall -pedantic, MSVC17
*/

typedef int matrix_data_t; /* matrix data type */

void transpose(const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void transpose_inplace(matrix_data_t* data, int n );
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void rotate_inplace(int direction, matrix_data_t* data, int n);
void reverse_rows(matrix_data_t* data, int rows, int cols);
void reverse_cols(matrix_data_t* data, int rows, int cols);

/* test/compare fn */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols );

/* TESTS/USAGE */
void transpose_test() {

matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };/* 3x3 square, odd length side */
matrix_data_t sq3x3_cpy[9];
matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };/* 2D 3x3 square */
matrix_data_t sq3x3_2D_copy[3][3];

/* expected test values */
const matrix_data_t sq3x3_orig[9] = { 0,1,2,3,4,5,6,7,8 };
const matrix_data_t sq3x3_transposed[9] = { 0,3,6,1,4,7,2,5,8};

matrix_data_t sq4x4[16]= { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };/* 4x4 square, even length*/
const matrix_data_t sq4x4_orig[16] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
const matrix_data_t sq4x4_transposed[16] = { 0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15 };

/* 2x3 rectangle */
const matrix_data_t r2x3_orig[6] = { 0,1,2,3,4,5 };
const matrix_data_t r2x3_transposed[6] = { 0,3,1,4,2,5 };
matrix_data_t r2x3_copy[6];

matrix_data_t r2x3_2D[2][3] = { {0,1,2},{3,4,5} }; /* 2x3 2D rectangle */
matrix_data_t r2x3_2D_t[3][2];

/* matrix_data_t r3x2[6] = { 0,1,2,3,4,5 }; */
matrix_data_t r3x2_copy[6];
/* 3x2 rectangle */
const matrix_data_t r3x2_orig[6] = { 0,1,2,3,4,5 };
const matrix_data_t r3x2_transposed[6] = { 0,2,4,1,3,5 };

matrix_data_t r6x1[6] = { 0,1,2,3,4,5 }; /* 6x1 */
matrix_data_t r6x1_copy[6];

matrix_data_t r1x1[1] = { 0 }; /*1x1*/
matrix_data_t r1x1_copy[1];

/* 3x3 tests, 2D array tests */
transpose_inplace(sq3x3, 3); /* transpose in place */
assert(!test_cmp(sq3x3, sq3x3_transposed, 3, 3));
transpose_inplace(sq3x3, 3); /* transpose again */
assert(!test_cmp(sq3x3, sq3x3_orig, 3, 3));

transpose(sq3x3, sq3x3_cpy, 3, 3); /* transpose copy 3x3*/
assert(!test_cmp(sq3x3_cpy, sq3x3_transposed, 3, 3));

transpose((matrix_data_t*)sq3x3_2D, (matrix_data_t*)sq3x3_2D_copy, 3, 3); /* 2D array transpose/copy */
assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_transposed, 3, 3));
transpose_inplace((matrix_data_t*)sq3x3_2D_copy, 3); /* 2D array transpose in place */
assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_orig, 3, 3));

/* 4x4 tests */
transpose_inplace(sq4x4, 4); /* transpose in place */
assert(!test_cmp(sq4x4, sq4x4_transposed, 4,4));
transpose_inplace(sq4x4, 4); /* transpose again */
assert(!test_cmp(sq4x4, sq4x4_orig, 3, 3));

/* 2x3,3x2 tests */
transpose(r2x3_orig, r2x3_copy, 2, 3);
assert(!test_cmp(r2x3_copy, r2x3_transposed, 3, 2));

transpose(r3x2_orig, r3x2_copy, 3, 2);
assert(!test_cmp(r3x2_copy, r3x2_transposed, 2,3));

/* 2D array */
transpose((matrix_data_t*)r2x3_2D, (matrix_data_t*)r2x3_2D_t, 2, 3);
assert(!test_cmp((matrix_data_t*)r2x3_2D_t, r2x3_transposed, 3,2));

/* Nx1 test, 1x1 test */
transpose(r6x1, r6x1_copy, 6, 1);
assert(!test_cmp(r6x1_copy, r6x1, 1, 6));

transpose(r1x1, r1x1_copy, 1, 1);
assert(!test_cmp(r1x1_copy, r1x1, 1, 1));

}

void rotate_test() {

/* 3x3 square */
const matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };
const matrix_data_t sq3x3_r90[9] = { 6,3,0,7,4,1,8,5,2 };
const matrix_data_t sq3x3_180[9] = { 8,7,6,5,4,3,2,1,0 };
const matrix_data_t sq3x3_l90[9] = { 2,5,8,1,4,7,0,3,6 };
matrix_data_t sq3x3_copy[9];

/* 3x3 square, 2D */
matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };

/* 4x4, 2D */
matrix_data_t sq4x4[4][4] = { { 0,1,2,3 },{ 4,5,6,7 },{ 8,9,10,11 },{ 12,13,14,15 } };
matrix_data_t sq4x4_copy[4][4];
const matrix_data_t sq4x4_r90[16] = { 12,8,4,0,13,9,5,1,14,10,6,2,15,11,7,3 };
const matrix_data_t sq4x4_l90[16] = { 3,7,11,15,2,6,10,14,1,5,9,13,0,4,8,12 };
const matrix_data_t sq4x4_180[16] = { 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };

matrix_data_t r6[6] = { 0,1,2,3,4,5 }; /* rectangle with area of 6 (1x6,2x3,3x2, or 6x1) */
matrix_data_t r6_copy[6];
const matrix_data_t r1x6_r90[6] = { 0,1,2,3,4,5 };
const matrix_data_t r1x6_l90[6] = { 5,4,3,2,1,0 };
const matrix_data_t r1x6_180[6] = { 5,4,3,2,1,0 };

const matrix_data_t r2x3_r90[6] = { 3,0,4,1,5,2 };
const matrix_data_t r2x3_l90[6] = { 2,5,1,4,0,3 };
const matrix_data_t r2x3_180[6] = { 5,4,3,2,1,0 };

const matrix_data_t r3x2_r90[6] = { 4,2,0,5,3,1 };
const matrix_data_t r3x2_l90[6] = { 1,3,5,0,2,4 };
const matrix_data_t r3x2_180[6] = { 5,4,3,2,1,0 };

const matrix_data_t r6x1_r90[6] = { 5,4,3,2,1,0 };
const matrix_data_t r6x1_l90[6] = { 0,1,2,3,4,5 };
const matrix_data_t r6x1_180[6] = { 5,4,3,2,1,0 };

/* sq3x3 tests */
rotate(90, sq3x3, sq3x3_copy, 3, 3); /* +90 */
assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
rotate(-90, sq3x3, sq3x3_copy, 3, 3); /* -90 */
assert(!test_cmp(sq3x3_copy, sq3x3_l90, 3, 3));
rotate(180, sq3x3, sq3x3_copy, 3, 3); /* 180 */
assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
/* sq3x3 in-place rotations */
memcpy( sq3x3_copy, sq3x3, 3 * 3 * sizeof(matrix_data_t));
rotate_inplace(90, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
rotate_inplace(-90, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3)); /* back to 0 orientation */
rotate_inplace(180, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
rotate_inplace(-180, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3));
rotate_inplace(180, (matrix_data_t*)sq3x3_2D, 3);/* 2D test */
assert(!test_cmp((matrix_data_t*)sq3x3_2D, sq3x3_180, 3, 3));

/* sq4x4 */
rotate(90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_r90, 4, 4));
rotate(-90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_l90, 4, 4));
rotate(180, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_180, 4, 4));

/* r6 as 1x6 */
rotate(90, r6, r6_copy, 1, 6);
assert(!test_cmp(r6_copy, r1x6_r90, 1, 6));
rotate(-90, r6, r6_copy, 1, 6);
assert(!test_cmp(r6_copy, r1x6_l90, 1, 6));
rotate(180, r6, r6_copy, 1, 6);
assert(!test_cmp(r6_copy, r1x6_180, 1, 6));

/* r6 as 2x3 */
rotate(90, r6, r6_copy, 2, 3);
assert(!test_cmp(r6_copy, r2x3_r90, 2, 3));
rotate(-90, r6, r6_copy, 2, 3);
assert(!test_cmp(r6_copy, r2x3_l90, 2, 3));
rotate(180, r6, r6_copy, 2, 3);
assert(!test_cmp(r6_copy, r2x3_180, 2, 3));

/* r6 as 3x2 */
rotate(90, r6, r6_copy, 3, 2);
assert(!test_cmp(r6_copy, r3x2_r90, 3, 2));
rotate(-90, r6, r6_copy, 3, 2);
assert(!test_cmp(r6_copy, r3x2_l90, 3, 2));
rotate(180, r6, r6_copy, 3, 2);
assert(!test_cmp(r6_copy, r3x2_180, 3, 2));

/* r6 as 6x1 */
rotate(90, r6, r6_copy, 6, 1);
assert(!test_cmp(r6_copy, r6x1_r90, 6, 1));
rotate(-90, r6, r6_copy, 6, 1);
assert(!test_cmp(r6_copy, r6x1_l90, 6, 1));
rotate(180, r6, r6_copy, 6, 1);
assert(!test_cmp(r6_copy, r6x1_180, 6, 1));
}

/* test comparison fn, return 0 on match else non zero */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols) {

int r, c;

for (r = 0; r < rows; ++r) {
for (c = 0; c < cols; ++c) {
if ((lhs + r * cols)[c] != (rhs + r * cols)[c])
return -1;
}
}
return 0;
}

/*
Reverse values in place of each row in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] -> [C B A]
[D E F] [F E D]
*/
void reverse_rows(matrix_data_t* data, int rows, int cols) {

int r, c;
matrix_data_t temp;
matrix_data_t* pRow = NULL;

for (r = 0; r < rows; ++r) {
pRow = (data + r * cols);
for (c = 0; c < (int)(cols / 2); ++c) { /* explicit truncate */
temp = pRow[c];
pRow[c] = pRow[cols - 1 - c];
pRow[cols - 1 - c] = temp;
}
}
}

/*
Reverse values in place of each column in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] -> [D E F]
[D E F] [A B C]
*/
void reverse_cols(matrix_data_t* data, int rows, int cols) {

int r, c;
matrix_data_t temp;
matrix_data_t* pRowA = NULL;
matrix_data_t* pRowB = NULL;

for (c = 0; c < cols; ++c) {
for (r = 0; r < (int)(rows / 2); ++r) { /* explicit truncate */
pRowA = data + r * cols;
pRowB = data + cols * (rows - 1 - r);
temp = pRowA[c];
pRowA[c] = pRowB[c];
pRowB[c] = temp;
}
}
}

/* Transpose NxM matrix to MxN matrix in O(n) time */
void transpose(const matrix_data_t* src, matrix_data_t* dst, int N, int M) {

int i;
for (i = 0; i<N*M; ++i) dst[(i%M)*N + (i / M)] = src[i]; /* one-liner version */

/*
expanded version of one-liner: calculate XY based on array index, then convert that to YX array index
int i,j,x,y;
for (i = 0; i < N*M; ++i) {
x = i % M;
y = (int)(i / M);
j = x * N + y;
dst[j] = src[i];
}
*/

/*
nested for loop version
using ptr arithmetic to get proper row/column
this is really just dst[col][row]=src[row][col]

int r, c;

for (r = 0; r < rows; ++r) {
for (c = 0; c < cols; ++c) {
(dst + c * rows)[r] = (src + r * cols)[c];
}
}
*/
}

/*
Transpose NxN matrix in place
*/
void transpose_inplace(matrix_data_t* data, int N ) {

int r, c;
matrix_data_t temp;

for (r = 0; r < N; ++r) {
for (c = r; c < N; ++c) { /*start at column=row*/
/* using ptr arithmetic to get proper row/column */
/* this is really just
temp=dst[col][row];
dst[col][row]=src[row][col];
src[row][col]=temp;
*/
temp = (data + c * N)[r];
(data + c * N)[r] = (data + r * N)[c];
(data + r * N)[c] = temp;
}
}
}

/*
Rotate 1D or 2D src matrix to dst matrix in a direction (90,180,-90)
Precondition: src and dst are 2d matrices with dimensions src[rows][cols] and dst[cols][rows] or 1D pointers with logical rows/cols
*/
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols) {

switch (direction) {
case -90:
transpose(src, dst, rows, cols);
reverse_cols(dst, cols, rows);
break;
case 90:
transpose(src, dst, rows, cols);
reverse_rows(dst, cols, rows);
break;
case 180:
case -180:
/* bit copy to dst, use in-place reversals */
memcpy(dst, src, rows*cols*sizeof(matrix_data_t));
reverse_cols(dst, cols, rows);
reverse_rows(dst, cols, rows);
break;
}
}

/*
Rotate array in a direction.
Array must be NxN 2D or 1D array with logical rows/cols
Direction can be (90,180,-90,-180)
*/
void rotate_inplace( int direction, matrix_data_t* data, int n) {

switch (direction) {
case -90:
transpose_inplace(data, n);
reverse_cols(data, n, n);
break;
case 90:
transpose_inplace(data, n);
reverse_rows(data, n, n);
break;
case 180:
case -180:
reverse_cols(data, n, n);
reverse_rows(data, n, n);
break;
}
}

下面是一个javascript解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

const transpose = m => m[0].map((x,i) => m.map(x => x[i]));

a: // original matrix
123
456
789

transpose(a).reverse(); // rotate 90 degrees counter clockwise
369
258
147

transpose(a.slice().reverse()); // rotate 90 degrees clockwise
741
852
963

transpose(transpose(a.slice().reverse()).slice().reverse())
// rotate 180 degrees
987
654
321

下面是递归的PHP方法：

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

$m = array();
$m[0] = array('a', 'b', 'c');
$m[1] = array('d', 'e', 'f');
$m[2] = array('g', 'h', 'i');
$newMatrix = array();

function rotateMatrix($m, $i = 0, &$newMatrix)
{
foreach ($m as $chunk) {
$newChunk[] = $chunk[$i];
}
$newMatrix[] = array_reverse($newChunk);
$i++;

if ($i < count($m)) {
rotateMatrix($m, $i, $newMatrix);
}
}

rotateMatrix($m, 0, $newMatrix);
echo '[cc]';
var_dump($newMatrix);
echo '[cc]';

这里是Java语言：

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

public static void rotateInPlace(int[][] m) {
for(int layer = 0; layer < m.length/2; layer++){
int first = layer;
int last = m.length - 1 - first;
for(int i = first; i < last; i ++){
int offset = i - first;
int top = m[first][i];
m[first][i] = m[last - offset][first];
m[last - offset][first] = m[last][last - offset];
m[last][last - offset] = m[i][last];
m[i][last] = top;
}
}
}

在爪哇

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
26
27
28
29
30
31
32
33
34
35
36
37

public class Matrix {
/* Author Shrikant Dande */
private static void showMatrix(int[][] arr,int rows,int col){

for(int i =0 ;i<rows;i++){
for(int j =0 ;j<col;j++){
System.out.print(arr[i][j]+"");
}
System.out.println();
}

}

private static void rotateMatrix(int[][] arr,int rows,int col){

int[][] tempArr = new int[4][4];
for(int i =0 ;i<rows;i++){
for(int j =0 ;j<col;j++){
tempArr[i][j] = arr[rows-1-j][i];
System.out.print(tempArr[i][j]+"");
}
System.out.println();
}

}
public static void main(String[] args) {
int[][] arr = { {1, 2, 3, 4},
{5, 6, 7, 8},
{9, 1, 2, 5},
{7, 4, 8, 9}};
int rows = 4,col = 4;

showMatrix(arr, rows, col);
System.out.println("------------------------------------------------");
rotateMatrix(arr, rows, col);

}

}

可以非常清晰地递归完成，这是我在Golang中的实现！

在Go Golang中递归地旋转nxn矩阵，无需额外内存

1
2
3
4
5
6
7
8
9
10

func rot90(a [][]int) {
n := len(a)
if n == 1 {
return
}
for i := 0; i < n; i++ {
a[0][i], a[n-1-i][n-1] = a[n-1-i][n-1], a[0][i]
}
rot90(a[1:])
}

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
26
27
28
29
30
31

public static void rotateMatrix(int[,] matrix)
{
//C#, to rotate an N*N matrix in place
int n = matrix.GetLength(0);
int layers = n / 2;
int temp, temp2;

for (int i = 0; i < layers; i++) // for a 5 * 5 matrix, layers will be 2, since at layer three there would be only one element, (2,2), and we do not need to rotate it with itself
{
int offset = 0;
while (offset < n - 2 * i - 1)
{
// top right <- top left
temp = matrix[i + offset, n - i - 1]; //top right value when offset is zero
matrix[i + offset, n - i - 1] = matrix[i, i + offset];

//bottom right <- top right
temp2 = matrix[n - i - 1, n - i - 1 - offset]; //bottom right value when offset is zero
matrix[n - i - 1, n - i - 1 - offset] = temp;

//bottom left <- bottom right
temp = matrix[n - i - 1 - offset, i];
matrix[n - i - 1 - offset, i] = temp2;

//top left <- bottom left
matrix[i, i + offset] = temp;

offset++;
}
}
}

这里有一个C静态的通用方法，可以为您工作。变量的名称很好，所以您可以很容易地理解algorythm的概念。

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
26
27
28
29
30
31

private static T[,] Rotate180 <T> (T[,] matrix)
{
var height = matrix.GetLength (0);
var width = matrix.GetLength (1);
var answer = new T[height, width];

for (int y = 0; y < height / 2; y++)
{
int topY = y;
int bottomY = height - 1 - y;
for (int topX = 0; topX < width; topX++)
{
var bottomX = width - topX - 1;
answer[topY, topX] = matrix[bottomY, bottomX];
answer[bottomY, bottomX] = matrix[topY, topX];
}
}

if (height % 2 == 0)
return answer;

var centerY = height / 2;
for (int leftX = 0; leftX < Mathf.CeilToInt(width / 2f); leftX++)
{
var rightX = width - 1 - leftX;
answer[centerY, leftX] = matrix[centerY, rightX];
answer[centerY, rightX] = matrix[centerY, leftX];
}

return answer;
}

对于就地旋转，不可能比O(n^2)更快，因为如果我们要旋转矩阵，不管您正在执行什么算法，我们都必须至少接触一次所有n^2元素。

这是将数组旋转90度的简单C代码。希望这有帮助。

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
26
27
28
29

#include <stdio.h>

void main(){
int arr[3][4] = {85, 2, 85, 4,
85, 6, 7, 85,
9, 85, 11, 12};

int arr1[4][3];

int i = 0, j = 0;

for(i=0;i<4;i++){
int k = 2;//k = (number of columns in the new array arr1 - 1)
for(j=0;j<3;j++){
arr1[i][j]=arr[k][i];
k--;
}
}

int l, m;
for(l=0;l<4;l++){
for(m=0;m<3;m++){
printf("%d", arr1[l][m]);
}
printf("
");
}
}//end main

这是最近被高估的面试问题。

我的建议是：不要让面试官把你和他们解决这个问题的疯狂建议混淆了。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列索引示例如下：

1
2
3
4
5
6
7
8
9

30 --> 00
20 --> 01
10 --> 02
00 --> 03

31 --> 10
21 --> 11
11 --> 12
01 --> 13

注意旋转后的数字模式。

下面提供了一个干净的Java解决方案。它经过测试，并且工作：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

Input:
M A C P
B N L D
Y E T S
I W R Z

Output:
I Y B M
W E N A
R T L C
Z S D P

/**
* (c) @author"G A N MOHIM"
* Oct 3, 2015
* RotateArrayNintyDegree.java
*/
package rotatearray;

public class RotateArrayNintyDegree {

public char[][] rotateArrayNinetyDegree(char[][] input) {
int k; // k is used to generate index for output array

char[][] output = new char[input.length] [input[0].length];

for (int i = 0; i < input.length; i++) {
k = 0;
for (int j = input.length-1; j >= 0; j--) {
output[i][k] = input[j][i]; // note how i is used as column index, and j as row
k++;
}
}

return output;
}

public void printArray(char[][] charArray) {
for (int i = 0; i < charArray.length; i++) {
for (int j = 0; j < charArray[0].length; j++) {
System.out.print(charArray[i][j] +"");
}
System.out.println();
}

}

public static void main(String[] args) {
char[][] input =
{ {'M', 'A', 'C', 'P'},
{'B', 'N', 'L', 'D'},
{'Y', 'E', 'T', 'S'},
{'I', 'W', 'R', 'Z'}
};

char[][] output = new char[input.length] [input[0].length];

RotateArrayNintyDegree rotationObj = new RotateArrayNintyDegree();
rotationObj.printArray(input);

System.out.println("
");
output = rotationObj.rotateArrayNinetyDegree(input);
rotationObj.printArray(output);

}

}

使用矢量矢量进行按时钟方向90度旋转。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<iostream>
#include<vector>
#include
using namespace std;
//Rotate a Matrix by 90 degrees
void rotateMatrix(vector<vector<int> > &matrix){
int n=matrix.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n;i++){
reverse(matrix[i].begin(),matrix[i].end());
}
}

int main(){

int n;
cout<<"enter the size of the matrix:"<<endl;
while (cin >> n) {
vector< vector<int> > m;
cout<<"enter the elements"<<endl;
for (int i = 0; i < n; i++) {
m.push_back(vector<int>(n));
for (int j = 0; j < n; j++)
scanf("%d", &m[i][j]);
}
cout<<"the rotated matrix is:"<<endl;
rotateMatrix(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << m[i][j] << ' ';
cout << endl;
}
}
return 0;
}

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

/* 90-degree clockwise:
temp_array = left_col
left_col = bottom_row
bottom_row = reverse(right_col)
reverse(right_col) = reverse(top_row)
reverse(top_row) = temp_array
*/
void RotateClockwise90(int ** arr, int lo, int hi) {

if (lo >= hi)
return;

for (int i=lo; i<hi; i++) {
int j = lo+hi-i;
int temp = arr[i][lo];
arr[i][lo] = arr[hi][i];
arr[hi][i] = arr[j][hi];
arr[j][hi] = arr[lo][j];
arr[lo][j] = temp;
}

RotateClockwise90(arr, lo+1, hi-1);
}

将矩阵旋转90度的javascript解决方案：

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

PHP:

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

如果需要将矩形二维数组旋转90度，请在上面的代码之前或之后(取决于所需的旋转方向)添加以下行：

1	$array = array_reverse($array);

1
2
3
4
5
6
7
8
9
10

#!/usr/bin/env python

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

# Rotate matrix 90 degrees...
for i in map(None,*original[::-1]):
print str(i) + '
'

这会使侧面旋转90度(即123(顶部)现在是741(左侧)。

这个python解决方案可以工作，因为它使用带有负步骤的切片来反转行顺序(将7排在最前面)

1
2
3

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

然后，它使用map(和隐含的identity函数一起使用，后者是map的结果，其中none作为第一个参数)和*按顺序解包所有元素，重新组合列(即，第一个元素放在一个元组中，第二个元素放在一个元组中，依此类推)。您有效地获得返回的以下重新分组：

1
2
3

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

对于新手程序员，在普通C++中。(Borland材料)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include<iostream.h>
#include<conio.h>

int main()
{
clrscr();

int arr[10][10]; // 2d array that holds input elements
int result[10][10]; //holds result

int m,n; //rows and columns of arr[][]
int x,y; //rows and columns of result[][]

int i,j; //loop variables
int t; //temporary , holds data while conversion

cout<<"Enter no. of rows and columns of array:";
cin>>m>>n;
cout<<"
Enter elements of array:

";
for(i = 0; i < m; i++)
{
for(j = 0; j<n ; j++)
{
cin>>arr[i][j]; // input array elements from user
}
}

//rotating matrix by +90 degrees

x = n ; //for non-square matrix
y = m ;

for(i = 0; i < x; i++)
{ t = m-1; // to create required array bounds
for(j = 0; j < y; j++)
{
result[i][j] = arr[t][i];
t--;
}
}

//print result

cout<<"
Rotated matrix is:

";
for(i = 0; i < x; i++)
{
for(j = 0; j < y; j++)
{
cout<<result[i][j]<<"";
}
cout<<"
";
}

getch();
return 0;
}

@dimple发送的伟大算法的C示例代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

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

using System.IO;
using System;

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

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

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

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

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

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

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

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

尝试我的库abacustil:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

@Test
public void test_42519() throws Exception {
final IntMatrix matrix = IntMatrix.range(0, 16).reshape(4);

N.println("======= original =======================");
matrix.println();
// print out:
// [0, 1, 2, 3]
// [4, 5, 6, 7]
// [8, 9, 10, 11]
// [12, 13, 14, 15]

N.println("======= rotate 90 ======================");
matrix.rotate90().println();
// print out:
// [12, 8, 4, 0]
// [13, 9, 5, 1]
// [14, 10, 6, 2]
// [15, 11, 7, 3]

N.println("======= rotate 180 =====================");
matrix.rotate180().println();
// print out:
// [15, 14, 13, 12]
// [11, 10, 9, 8]
// [7, 6, 5, 4]
// [3, 2, 1, 0]

N.println("======= rotate 270 ======================");
matrix.rotate270().println();
// print out:
// [3, 7, 11, 15]
// [2, 6, 10, 14]
// [1, 5, 9, 13]
// [0, 4, 8, 12]

N.println("======= transpose =======================");
matrix.transpose().println();
// print out:
// [0, 4, 8, 12]
// [1, 5, 9, 13]
// [2, 6, 10, 14]
// [3, 7, 11, 15]

final IntMatrix bigMatrix = IntMatrix.range(0, 10000_0000).reshape(10000);

// It take about 2 seconds to rotate 10000 X 10000 matrix.
Profiler.run(1, 2, 3,"sequential", () -> bigMatrix.rotate90()).printResult();

// Want faster? Go parallel. 1 second to rotate 10000 X 10000 matrix.
final int[][] a = bigMatrix.array();
final int[][] c = new int[a[0].length][a.length];
final int n = a.length;
final int threadNum = 4;

Profiler.run(1, 2, 3,"parallel", () -> {
IntStream.range(0, n).parallel(threadNum).forEach(i -> {
for (int j = 0; j < n; j++) {
c[i][j] = a[n - j - 1][i];
}
});
}).printResult();
}

算法的O(1)内存：

rotate外-大多数的数据，然后你可以得到以下结果：

1
2
3
4

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

做这个旋转，我们知道