受到Raymond Chen 帖子的启发，假设您有一个 4x4 二维数组，编写一个将其旋转 90 度的函数。Raymond 链接到伪代码中的解决方案，但我想看看一些真实世界的东西。
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
变成：
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
更新：尼克的回答是最直接的，但有没有办法比 n^2 做得更好？如果矩阵是 10000x10000 怎么办？
O(n^2) 时间和 O(1) 空间算法（没有任何变通方法和手帕的东西！）
旋转 +90：
旋转 -90：
方法一：
方法二：
旋转 +180：
方法一：旋转+90两次
方法2：反转每一行，然后反转每一列（转置）
旋转 -180：
方法一：旋转两次-90
方法2：反转每一列，然后反转每一行
方法3：旋转+180，因为它们是相同的
我想补充一点细节。在这个答案中，关键概念被重复，节奏缓慢且有意重复。这里提供的解决方案在语法上并不是最紧凑的，但是，它适用于那些希望了解什么是矩阵旋转以及由此产生的实现的人。
首先，什么是矩阵？出于此答案的目的，矩阵只是宽度和高度相同的网格。请注意，矩阵的宽度和高度可以不同，但为简单起见，本教程仅考虑宽度和高度相等的矩阵（方形矩阵）。是的，矩阵是矩阵的复数。
示例矩阵是：2×2、3×3 或 5×5。或者，更一般地，N×N。2×2 矩阵将有 4 个正方形，因为 2×2=4。5×5 矩阵将有 25 个正方形，因为 5×5=25。每个方格称为一个元素或条目。.我们将在下图中用句点 ( ) 表示每个元素：
2×2矩阵
. .
. .
3×3矩阵
. . .
. . .
. . .
4×4矩阵
. . . .
. . . .
. . . .
. . . .
那么，旋转矩阵是什么意思呢？让我们取一个 2×2 矩阵并在每个元素中放入一些数字，以便可以观察到旋转：
0 1
2 3
将其旋转 90 度给我们：
2 0
3 1
我们确实将整个矩阵向右转动了一次，就像转动汽车的方向盘一样。考虑将矩阵“倾斜”到其右侧可能会有所帮助。我们想用 Python 编写一个函数，它接受一个矩阵并将其向右旋转一次。函数签名将是：
def rotate(matrix):
# Algorithm goes here.
矩阵将使用二维数组定义：
matrix = [
[0,1],
[2,3]
]
因此，第一个索引位置访问该行。第二个索引位置访问该列：
matrix[row][column]
我们将定义一个实用函数来打印矩阵。
def print_matrix(matrix):
for row in matrix:
print row
旋转矩阵的一种方法是一次旋转一层。但什么是层？想想洋葱。就像洋葱的层一样，随着每一层被移除，我们向中心移动。其他类比是俄罗斯套娃或传递包裹的游戏。
矩阵的宽度和高度决定了该矩阵中的层数。让我们为每一层使用不同的符号：
一个 2×2 矩阵有 1 层
. .
. .
一个 3×3 矩阵有 2 层
. . .
. x .
. . .
一个 4×4 矩阵有 2 层
. . . .
. x x .
. x x .
. . . .
一个 5×5 矩阵有 3 层
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
一个 6×6 矩阵有 3 层
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
一个 7×7 矩阵有 4 层
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
您可能会注意到，将矩阵的宽度和高度加一并不总是增加层数。采用上述矩阵并将层和尺寸制成表格，我们看到层数每增加两次宽度和高度就会增加一次：
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
但是，并非所有层都需要旋转。一个 1×1 的矩阵在旋转前后是一样的。无论整体矩阵有多大，中心的 1×1 层在旋转前后始终相同：
+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 | 1 | 0 |
| 2×2 | 1 | 1 |
| 3×3 | 2 | 1 |
| 4×4 | 2 | 2 |
| 5×5 | 3 | 2 |
| 6×6 | 3 | 3 |
| 7×7 | 4 | 3 |
+-----+--------+------------------+
给定 N×N 矩阵，我们如何以编程方式确定需要旋转的层数？如果我们将宽度或高度除以二并忽略余数，我们会得到以下结果。
+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers | N/2 |
+-----+--------+------------------+---------+
| 1×1 | 1 | 0 | 1/2 = 0 |
| 2×2 | 1 | 1 | 2/2 = 1 |
| 3×3 | 2 | 1 | 3/2 = 1 |
| 4×4 | 2 | 2 | 4/2 = 2 |
| 5×5 | 3 | 2 | 5/2 = 2 |
| 6×6 | 3 | 3 | 6/2 = 3 |
| 7×7 | 4 | 3 | 7/2 = 3 |
+-----+--------+------------------+---------+
注意如何N/2匹配需要旋转的层数？有时可旋转的层数比矩阵中的总层数少一。当最内层仅由一个元素（即 1×1 矩阵）形成并且因此不需要旋转时，就会发生这种情况。它只是被忽略了。
毫无疑问，我们在函数中需要这些信息来旋转矩阵，所以现在让我们添加它：
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
现在我们知道什么是层以及如何确定实际需要旋转的层数，我们如何隔离单个层以便我们可以旋转它？首先，我们从最外层向内到最内层检查矩阵。一个 5×5 的矩阵共有三层，其中两层需要旋转：
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
我们先来看列。定义最外层的列的位置，假设我们从 0 开始计数，分别是 0 和 4：
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 和 4 也是最外层的行的位置。
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
由于宽度和高度相同，因此总是如此。因此，我们可以只用两个值（而不是四个）来定义层的列和行位置。
向内移动到第二层，列的位置是 1 和 3。而且，是的，你猜对了，行也是一样的。重要的是要了解当向内移动到下一层时，我们必须同时增加和减少行和列的位置。
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
因此，为了检查每一层，我们需要一个循环，其中包含表示从最外层开始向内移动的递增和递减计数器。我们将其称为“层循环”。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)
# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate(matrix)
上面的代码循环遍历需要旋转的任何层的（行和列）位置。
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
我们现在有一个循环来提供每一层的行和列的位置。变量first和last标识第一行和最后一行和列的索引位置。回顾我们的行表和列表：
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
所以我们可以浏览矩阵的各个层。现在我们需要一种在层内导航的方法，以便我们可以在该层周围移动元素。请注意，元素永远不会从一层“跳转”到另一层，但它们确实会在各自的层内移动。
旋转层中的每个元素会旋转整个层。旋转矩阵中的所有层会旋转整个矩阵。这句话很重要，所以在继续之前请尽量理解它。
现在，我们需要一种实际移动元素的方法，即旋转每个元素，然后旋转层，最后旋转矩阵。为简单起见，我们将恢复为 3x3 矩阵——它有一个可旋转层。
0 1 2
3 4 5
6 7 8
我们的层循环提供第一列和最后一列以及第一行和最后一行的索引：
+-----+-------+
| Col | 0 1 2 |
+-----+-------+
| | 0 1 2 |
| | 3 4 5 |
| | 6 7 8 |
+-----+-------+
+-----+-------+
| Row | |
+-----+-------+
| 0 | 0 1 2 |
| 1 | 3 4 5 |
| 2 | 6 7 8 |
+-----+-------+
因为我们的矩阵总是正方形的，所以我们只需要两个变量first和last，因为行和列的索引位置是相同的。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# We want to move within a layer here.
变量 first 和 last 可以很容易地用于引用矩阵的四个角。这是因为角本身可以使用和的各种排列来定义first（last这些变量没有减法、加法或偏移）：
+---------------+-------------------+-------------+
| Corner | Position | 3x3 Values |
+---------------+-------------------+-------------+
| top left | (first, first) | (0,0) |
| top right | (first, last) | (0,2) |
| bottom right | (last, last) | (2,2) |
| bottom left | (last, first) | (2,0) |
+---------------+-------------------+-------------+
出于这个原因，我们从外四个角开始旋转——我们将首先旋转它们。让我们用 突出显示它们*。
* 1 *
3 4 5
* 7 *
我们想*用*它的右边交换每个。因此，让我们继续打印仅使用first和的各种排列定义的角last：
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)
print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)
matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
rotate(matrix)
输出应该是：
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
现在我们可以很容易地从层循环中交换每个角：
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]
# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right
print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)
转角前的矩阵：
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
转角后的矩阵：
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
伟大的！我们已经成功地旋转了矩阵的每个角。但是，我们还没有旋转每一层中间的元素。显然，我们需要一种在层内迭代的方法。
问题是，到目前为止，我们函数中唯一的循环（我们的层循环）在每次迭代时都移动到下一层。由于我们的矩阵只有一个可旋转层，层循环仅在旋转角后退出。让我们看看一个更大的 5×5 矩阵（其中两层需要旋转）会发生什么。功能代码已省略，但和上面一样：
matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)
输出是：
[20, 1, 2, 3, 0]
[ 5, 16, 7, 6, 9]
[10, 11, 12, 13, 14]
[15, 18, 17, 8, 19]
[24, 21, 22, 23, 4]
最外层的角已旋转并不奇怪，但是，您可能还会注意到下一层（向内）的角也已旋转。这是有道理的。我们已经编写了代码来导航层并旋转每个层的角。这感觉像是进步，但不幸的是，我们必须退后一步。在前一个（外）层完全旋转之前，移动到下一层是没有好处的。也就是说，直到图层中的每个元素都已旋转。只旋转角落是不行的！
深吸一口气。我们需要另一个循环。一个嵌套循环也不少。新的嵌套循环将使用firstandlast变量以及偏移量在层内导航。我们将把这个新循环称为我们的“元素循环”。元素循环将访问顶行的每个元素、右侧的每个元素、底行的每个元素以及左侧的每个元素。
这听起来很复杂，但它很容易，因为我们为实现上述目的而递增和递减的次数在矩阵的所有四个边上保持不变。例如：
这意味着我们可以使用单个变量结合first和last变量在层内移动。可能需要注意的是，在顶行和右侧向下移动都需要递增。在沿着底部和左侧向上向后移动时，两者都需要递减。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)
print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)
现在我们只需要将顶部分配到右侧，将右侧分配到底部，将底部分配到左侧，将左侧分配到顶部。把这一切放在一起，我们得到：
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
for element in range(first, last):
offset = element - first
top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]
matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom
给定矩阵：
0, 1, 2
3, 4, 5
6, 7, 8
我们的rotate函数导致：
6, 3, 0
7, 4, 1
8, 5, 2
这是在 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;
}
Python：
rotated = list(zip(*original[::-1]))
和逆时针：
rotated_ccw = list(zip(*original))[::-1]
这是如何工作的：
zip(*original)将通过将列表中的相应项目堆叠到新列表中来交换二维数组的轴。（*运算符告诉函数将包含的列表分配到参数中）
>>> list(zip(*[[1,2,3],[4,5,6],[7,8,9]]))
[[1,4,7],[2,5,8],[3,6,9]]
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
最后，将两者结合将导致旋转变换。
位置的变化[::-1]将反转矩阵不同级别的列表。
这是一个在适当位置进行旋转而不是使用全新数组来保存结果的方法。我已经停止了数组的初始化并将其打印出来。这仅适用于方形数组，但它们可以是任何大小。内存开销等于数组的一个元素的大小，因此您可以根据需要旋转尽可能大的数组。
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;
}
}
这里有很多好的代码，但我只想从几何上展示发生了什么，这样你就可以更好地理解代码逻辑。这是我将如何处理这个问题。
首先，不要将此与非常容易的换位混淆..
基本的想法是将其视为层，我们一次旋转一层..
假设我们有一辆 4x4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
顺时针旋转 90 度后，我们得到
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
所以让我们分解一下，首先我们旋转 4 个角
1 4
13 16
然后我们旋转下面的菱形，它有点歪斜
2
8
9
15
然后是第二个斜钻石
3
5
12
14
这样就可以处理外边缘，所以基本上我们一次只做一个壳，直到
最后是中间的正方形（或者如果它很奇怪，只是最后一个不移动的元素）
6 7
10 11
所以现在让我们找出每一层的索引，假设我们总是使用最外层，我们正在做
[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]
以此类推，直到我们走到边缘的一半
所以一般来说模式是
[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
正如我在上一篇文章中所说，这是 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。对构造函数进行小的更改以创建一个新数组并将值复制到其中就可以解决这个问题。
虽然可能需要在适当的位置旋转数据（可能是为了更新物理存储的表示），但在数组访问上添加一层间接层（可能是接口）变得更简单并且可能更高效：
interface IReadableMatrix
{
int GetValue(int x, int y);
}
如果你Matrix已经实现了这个接口，那么它可以通过这样的装饰器类来旋转：
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
旋转 +90/-90/180 度、水平/垂直翻转和缩放都可以通过这种方式实现。
需要在您的特定场景中测量性能。然而，O(n^2) 操作现在已被 O(1) 调用替换。这是一个虚方法调用，比直接数组访问要慢，所以它取决于旋转后数组的使用频率。如果使用一次，那么这种方法肯定会赢。如果它被旋转然后在长时间运行的系统中使用了几天，那么就地旋转可能会表现得更好。这还取决于您是否可以接受前期费用。
与所有性能问题一样，测量、测量、测量！
这是 Java 中更好的版本：我已经为具有不同宽度和高度的矩阵制作了它
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
此代码基于 Nick Berardi 的帖子。
红宝石方式：.transpose.map &:reverse
已经有很多答案，我发现两个声称 O(1) 时间复杂度。真正的O (1) 算法是保持数组存储不变，并更改索引其元素的方式。这里的目标是它不消耗额外的内存，也不需要额外的时间来迭代数据。
90、-90 和 180 度的旋转是简单的转换，只要您知道 2D 数组中有多少行和列就可以执行；要将任何向量旋转 90 度，请交换轴并将 Y 轴取反。对于 -90 度，交换轴并将 X 轴取反。对于 180 度，否定两个轴而不交换。
进一步的转换是可能的，例如通过独立地否定轴来水平和/或垂直镜像。
这可以通过例如访问器方法来完成。下面的示例是 JavaScript 函数，但这些概念同样适用于所有语言。
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);此代码假定一个嵌套数组的数组，其中每个内部数组是一行。
该方法允许您读取（或写入）元素（甚至以随机顺序），就好像数组已被旋转或变换一样。现在只需选择要调用的正确函数，可能是通过引用，然后就可以了！
该概念可以扩展为通过访问器方法以附加方式（且非破坏性方式）应用转换。包括任意角度旋转和缩放。
一些人已经提出了涉及制作新数组的示例。
其他一些需要考虑的事情：
(a) 与其实际移动数据，不如简单地以不同方式遍历“旋转”数组。
(b) 就地进行旋转可能有点棘手。您将需要一些临时位置（可能大致等于一行或一列的大小）。有一篇关于就地转置的古老 ACM 论文（http://doi.acm.org/10.1145/355719.355729），但他们的示例代码是讨厌的 goto-laden FORTRAN。
附录：
http://doi.acm.org/10.1145/355611.355612是另一种据说更优越的就地转置算法。
尼克的答案也适用于 NxM 阵列，只需稍作修改（而不是 NxN）。
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
考虑这一点的一种方法是，您已将轴的中心 (0,0) 从左上角移动到右上角。你只是从一个转移到另一个。
时间 - 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;
}
}
}
这是我的 Ruby 版本（请注意，显示的值不同，但仍按描述旋转）。
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
输出：
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
这是java的空间旋转方法，仅适用于正方形。对于非方形二维数组，无论如何您都必须创建新数组。
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;
}
}
}
}
通过创建新数组来旋转任何大小的二维数组的代码：
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;
}
顺时针或逆时针旋转二维数组的常用方法。
1 2 3 7 8 9 7 4 1
4 5 6 => 4 5 6 => 8 5 2
7 8 9 1 2 3 9 6 3
void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
1 2 3 3 2 1 3 6 9
4 5 6 => 6 5 4 => 2 5 8
7 8 9 9 8 7 1 4 7
void anti_rotate(vector<vector<int> > &matrix) {
for (auto vi : matrix) reverse(vi.begin(), vi.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
在 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;
}
您可以通过3 个简单的步骤完成此操作：
1）假设我们有一个矩阵
1 2 3
4 5 6
7 8 9
2）取矩阵的转置
1 4 7
2 5 8
3 6 9
3）交换行以获得旋转矩阵
3 6 9
2 5 8
1 4 7
Java源代码：
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
输出：
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
PHP：
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
从 PHP5.6 开始，可以通过偷偷array_map()调用来执行数组转置。换句话说，列被转换为行。
代码：（演示）
$array = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 0, 1, 2],
[3, 4, 5, 6]
];
$transposed = array_map(null, ...$array);
$转置：
[
[1, 5, 9, 3],
[2, 6, 0, 4],
[3, 7, 1, 5],
[4, 8, 2, 6]
]
这是我的实现，在 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;
}
}
}
这是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;
}
}
}
该方法首先旋转最外层，然后依次移动到内层。
从线性的角度来看，考虑以下矩阵：
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
现在采取 A 转置
1 4 7
A' = 2 5 8
3 6 9
并考虑 A' 对 B 的作用，或 B 对 A' 的作用。
分别：
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
这对于任何 nxn 矩阵都是可扩展的。并在代码中快速应用这个概念：
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
将 [n,m] 二维数组向右旋转 90 度的 C# 代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
结果：
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
@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
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++ 方法，但在大数组中会有很大的内存开销。
For i:= 0 to X do
For j := 0 to X do
graphic[j][i] := graphic2[X-i][j]
X 是图形所在数组的大小。
#transpose 是 Ruby 的 Array 类的标准方法，因此：
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
该实现是用 C 编写的 n^2 转置函数。您可以在此处查看： http ://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose 选择“单击在“转置”旁边切换源”。
我记得比 O(n^2) 解决方案更好，但仅适用于特殊构造的矩阵（例如稀疏矩阵）
用于任何 M*N 矩阵的矩阵顺时针旋转 90 度的 C 代码
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
这是我对矩阵 90 度旋转的尝试，这是 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;
}
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;
}
这是我在 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;
}
}
}
运行时 O(N^2) 和内存 O(1) 的 NxN 矩阵的 Javascript 解决方案
function rotate90(matrix){
var length = matrix.length
for(var row = 0; row < (length / 2); row++){
for(var col = row; col < ( length - 1 - row); col++){
var tmpVal = matrix[row][col];
for(var i = 0; i < 4; i++){
var rowSwap = col;
var colSwap = (length - 1) - row;
var poppedVal = matrix[rowSwap][colSwap];
matrix[rowSwap][colSwap] = tmpVal;
tmpVal = poppedVal;
col = colSwap;
row = rowSwap;
}
}
}
}
很好的答案，但对于那些正在为此寻找 DRY 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);顺时针和逆时针的PHP解决方案
$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 "\n";
}
}
printMatrix( $aMatrix );
echo "\n";
$aNewMatrix = CounterClockwise( $aMatrix );
printMatrix( $aNewMatrix );
echo "\n";
$aNewMatrix = Clockwise( $aMatrix );
printMatrix( $aNewMatrix );
矩阵转置和旋转的 C 代码 (+/-90, +/-180)
`
#include <stdlib.h>
#include <memory.h>
#include <assert.h>
/*
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;
}
}
`
在蟒蛇中：
import numpy as np
a = np.array(
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 0, 1, 2],
[3, 4, 5, 6]
]
)
print(a)
print(b[::-1, :].T)
#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\n";
print(a,SIZE);
rotate( a,SIZE);
cout<<"the array after rotate\n";
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) 开销作为暂存空间（这不包括那些肮脏的 OOP 作弊者！）。这是一个使用 O(1) 内存的解决方案，将矩阵原地向右旋转 90 度。螺丝扩展性，这个吸盘跑得快！
#include <algorithm>
#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]);
}
免责声明：我实际上并没有对此进行测试。让我们玩打虫吧！
这是一种递归的PHP方式：
$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 '<pre>';
var_dump($newMatrix);
echo '<pre>';
我的旋转版本：
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];
}
在其中，我们将最后一列更改为第一行，等等。它可能不是最佳的，但易于理解。
这是一个Javascript解决方案：
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
基于过多的其他答案，我在 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<TValue>[][]result = new TValue[Columns, Rows]Matrix<TValue>ColumnsRows
public uint Columns
=> (uint)_values[0].Length;
public uint Rows
=> (uint)_values.Length;
当然，假设您更喜欢使用无符号索引；-)
所有这些都允许您指定它应该旋转多少次，以及它应该向左（如果小于零）还是向右（如果大于零）旋转。您可以改进它以检查实际度数的旋转，但是如果该值不是 90 的倍数，则您想抛出异常。使用该输入，您可以相应地更改方法：
public Matrix<TValue> Rotate(int rotation)
{
var _rotation = (double)rotation / 90d;
if (_rotation - Math.Floor(_rotation) > 0)
{
throw new NotSupportedException("A matrix may only be rotated by multiples of 90.").
}
rotation = (int)_rotation;
...
}
由于度double比更准确地表示int，但矩阵只能以 90 的倍数旋转，因此将参数对应于可以用所用数据结构准确表示的其他东西要直观得多。int非常完美，因为它可以告诉您将其旋转到某个单位 (90) 的次数以及方向。double很可能也可以告诉您，但它还包括此操作不支持的值（这本质上是违反直觉的）。
基于社区 wiki 算法和转置数组的这个 SO 答案，这里有一个 Swift 4 版本，可以将一些 2D 数组逆时针旋转 90 度。这假设matrix是一个二维数组：
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 方法时，此实现都会创建一个新数组，它根本不会改变原始数组。
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("]");
}
}
我可以用一个循环来做到这一点。时间复杂度看起来像O(K)，其中 K 是数组的所有项。以下是我在 JavaScript 中的做法：
首先，我们用单个数组表示 n^2 矩阵。然后，像这样遍历它：
/**
* Rotates matrix 90 degrees clockwise
* @param arr: the source array
* @param n: the array side (array is square n^2)
*/
function rotate (arr, n) {
var rotated = [], indexes = []
for (var i = 0; i < arr.length; i++) {
if (i < n)
indexes[i] = i * n + (n - 1)
else
indexes[i] = indexes[i - n] - 1
rotated[indexes[i]] = arr[i]
}
return rotated
}
基本上，我们转换源数组索引：
[0,1,2,3,4,5,6,7,8]=>[2,5,8,1,4,7,0,3,6]
然后，使用这个转换后indexes的数组，我们将实际值放入最终rotated数组中。
以下是一些测试用例：
//n=3
rotate([
1, 2, 3,
4, 5, 6,
7, 8, 9], 3))
//result:
[7, 4, 1,
8, 5, 2,
9, 6, 3]
//n=4
rotate([
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16], 4))
//result:
[13, 9, 5, 1,
14, 10, 6, 2,
15, 11, 7, 3,
16, 12, 8, 4]
//n=5
rotate([
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], 5))
//result:
[21, 16, 11, 6, 1,
22, 17, 12, 7, 2,
23, 18, 13, 8, 3,
24, 19, 14, 9, 4,
25, 20, 15, 10, 5]
在本征(C++) 中：
Eigen::Matrix2d mat;
mat << 1, 2,
3, 4;
std::cout << mat << "\n\n";
Eigen::Matrix2d r_plus_90 = mat.transpose().rowwise().reverse();
std::cout << r_plus_90 << "\n\n";
Eigen::Matrix2d r_minus_90 = mat.transpose().colwise().reverse();
std::cout << r_minus_90 << "\n\n";
Eigen::Matrix2d r_180 = mat.colwise().reverse().rowwise().reverse(); // +180 same as -180
std::cout << r_180 << "\n\n";
输出：
1 2
3 4
3 1
4 2
2 4
1 3
4 3
2 1
就地旋转不可能比 O(n^2) 快，因为如果我们想旋转矩阵，我们必须至少触摸所有 n^2 元素一次，不管是什么算法你正在实施。
对于新手程序员，使用纯 C++ 。（Borland 的东西）
#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<<"\nEnter elements of array: \n\n";
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<<"\nRotated matrix is: \n\n";
for(i = 0; i < x; i++)
{
for(j = 0; j < y; j++)
{
cout<<result[i][j]<<" ";
}
cout<<"\n";
}
getch();
return 0;
}
#!/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) + '\n'
这会导致侧面旋转 90 度（即 123（顶部）现在是 741（左侧）。
这个 Python 解决方案之所以有效，是因为它使用带有负步骤的切片来反转行顺序（将 7 带到顶部）
original = [ [7,8,9],
[4,5,6],
[1,2,3] ]
然后它使用 map （以及隐含的恒等函数，它是 map 的结果，第一个参数为 None ）和 * 依次解包所有元素，重新组合列（即第一个元素放在一个元组中，第二个元素一起放在一个元组中，依此类推）。您有效地得到返回以下重组：
original = [[7,8,9],
[4,5,6],
[1,2,3]]
PHP：
array_unshift($array, null);
$array = call_user_func_array("array_map", $array);
如果您需要将矩形二维数组旋转 90 度，请在上面的代码之前或之后（取决于您需要的旋转方向）添加以下行：
$array = array_reverse($array);
将矩阵旋转 90 度的 JavaScript 解决方案：
function rotateBy90(m) {
var length = m.length;
//for each layer of the matrix
for (var first = 0; first < length >> 1; first++) {
var last = length - 1 - first;
for (var i = first; i < last; i++) {
var top = m[first][i]; //store top
m[first][i] = m[last - i][first]; //top = left
m[last - i][first] = m[last][last - i]; //left = bottom
m[last][last - i] = m[i][last]; //bottom = right
m[i][last] = top; //right = top
}
}
return m;
}
/* 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 度。
#include<iostream>
#include<vector>
#include<algorithm>
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;
}
这些天来，这是一个被高估的面试问题。
我的建议是：不要让面试官用他们关于解决这个问题的疯狂建议来混淆你。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列索引示例如下所示：
30 --> 00
20 --> 01
10 --> 02
00 --> 03
31 --> 10
21 --> 11
11 --> 12
01 --> 13
注意旋转后的数字模式。
下面提供了一个简洁的 Java 解决方案。它经过测试，并且有效：
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("\n");
output = rotationObj.rotateArrayNinetyDegree(input);
rotationObj.printArray(output);
}
}
这是Java：
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;
}
}
}
这是将数组旋转 90 度的简单 C 代码。希望这可以帮助。
#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("\n");
}
}//end main
我为 @dimple 发送的出色算法的C#示例代码：
/* 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
*/
这是为您完成工作的 C# 静态泛型方法。变量的名字很好，所以你可以很容易地理解算法的概念。
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;
}
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++;
}
}
}
可以很干净地递归完成，这是我在 golang 中的实现！
在没有额外内存的情况下递归地在 go golang 中旋转 nxn 矩阵
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:])
}
在 Java 中
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);
}
}
O(1) 内存算法：
旋转最外面的数据，然后你可以得到以下结果：
[3][9][5][1]
[4][6][7][2]
[5][0][1][3]
[6][2][8][4]
要进行这种旋转，我们知道
dest[j][n-1-i] = src[i][j]
观察以下： a(0,0) -> a(0,3) a(0,3) -> a(3,3) a(3,3) -> a(3,0) a(3,0 ) -> a(0,0)
因此它是一个圆圈，您可以在一个循环中旋转 N 个元素。执行此 N-1 循环，然后您可以旋转最外面的元素。
因此我们可以总结如下：
function rotate(array, N)
{
Rotate outer-most data
rotate a new array with N-2 or you can do the similar action following step1
}
试试我的图书馆AbacusUtil：
@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();
}