https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
灵感来自 雷蒙德·陈的帖子, ，假设您有一个 4x4 二维数组，请编写一个将其旋转 90 度的函数。雷蒙德链接到伪代码中的解决方案，但我想看看一些现实世界的东西。
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
变成：
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
更新: ：Nick的答案是最直接的，但是有没有比n^2更好的方法呢？如果矩阵是 10000x10000 呢？
解决方案
这是 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;
}
其他提示
O(n^2) 时间和 O(1) 空间算法 （没有任何解决方法和小伎俩！）
旋转 +90：
- 转置
- 反转每一行
旋转-90：
方法一：
- 转置
- 反转每列
方法二：
- 反转每一行
- 转置
旋转 +180：
方法一: ：+90 旋转两次
方法2: ：反转每一行，然后反转每一列（转置）
旋转-180：
方法一: ：-90 旋转两次
方法2: ：反转每一列，然后反转每一行
方法三: ：旋转+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]
最外层的角已旋转，这并不奇怪，但是，您可能还会注意到下一层（向内）的角也已旋转。这是有道理的。我们编写了代码来浏览图层以及旋转每层的角。这感觉像是进步，但不幸的是我们必须后退一步。在上一层（外层）完全旋转之前，移动到下一层是没有用的。也就是说，直到层中的每个元素都已旋转。只旋转角是不行的！
深吸一口气。我们需要另一个循环。嵌套循环也不少。新的嵌套循环将使用 first 和 last 变量，加上在图层内导航的偏移量。我们将这个新循环称为“元素循环”。元素循环将访问沿顶行的每个元素、沿右侧的每个元素、沿底行的每个元素以及沿左侧的每个元素。
- 向前行驶，沿着顶行需要列索引进行递增。
- 向下移动右侧需要递增行索引。
- 向后沿底部移动需要减少列索引。
- 向上移动左侧需要降低行索引。
这听起来很复杂，但它很容易，因为我们为实现上述目的而增加和减少的次数在矩阵的所有四个边上保持相同。例如：
- 将 1 个元素移过顶行。
- 向右下移 1 个元素。
- 沿底行向后移动 1 个元素。
- 向左侧向上移动 1 个元素。
这意味着我们可以将单个变量与 first 和 last 在层内移动的变量。注意到穿过顶行和向下移动右侧都需要递增可能会有所帮助。沿着底部向后移动和向左侧向上移动都需要递减。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top_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)
现在我们只需要将顶部分配给右侧，将右侧分配给底部，将底部分配给左侧，将左侧分配给顶部。把这些放在一起我们得到：
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
Python：
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
便宜，我知道。
以及逆时针方向：
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
这是如何运作的： （评论中要求）
zip(*original) 将通过将列表中的相应项目堆叠到新列表中来交换二维数组的轴。（这 * 运算符告诉函数将包含的列表分配到参数中）
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
这 [::-1] 语句反转数组元素（请参见 扩展切片).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
最后，将两者结合起来将产生旋转变换。
安置的变化 [::-1] 将反转矩阵不同级别的列表。
这是就地进行旋转的方法，而不是使用全新的数组来保存结果。我已经停止了数组的初始化并将其打印出来。这仅适用于方形数组，但它们可以是任何大小。内存开销等于数组一个元素的大小，因此您可以根据需要旋转任意大的数组。
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;
}
好的，我举手，它在旋转时实际上并没有对原始数组做任何修改。但是，在面向对象系统中，只要对象看起来像是已轮换到类的客户端，这并不重要。目前，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 中更好的版本：我已经为具有不同宽度和高度的矩阵制作了它
- h 这里是旋转后矩阵的高度
- w 这里是旋转后矩阵的宽度
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
此代码基于 Nick Berardi 的帖子。
红宝石方式： .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;
}
实现酒窝的 +90 伪代码（例如在 JavaScript 中转置然后反转每一行：
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
你可以在 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
爪哇 源代码 为了这：
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);
}
}
?>
这是我的实现，在 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
这对于任何 n x n 矩阵都是可扩展的。并在代码中快速应用这个概念：
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
将 [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
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) 解决方案更好，但仅限于特殊构造的矩阵（例如稀疏矩阵）
用于矩阵顺时针旋转 90 度的 C 代码 IN PLACE 对于任何 M*N 矩阵
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
这是我在 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;
}
}
}
这是我对矩阵 90 度旋转的尝试，这是 C 中的两步解决方案。首先将矩阵转置到位，然后交换列。
#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;
}
@达戈里姆：噢，伙计。我一直把这个当作一个很好的“我很无聊，我能思考什么”的谜题。我想出了我的就地换位代码，但到这里发现你的代码与我的几乎相同......啊，好吧。这是 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++ 方法，但大数组会产生很大的内存开销。
