灵感来自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:
方法1:
颠倒
反转每一列
方法2:
反转每一行
颠倒
旋转+180:
方法1:旋转+90两次
方法2:反转每一行然后反转每一列(Transpose)
旋转-180:
方法1:旋转-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
旋转矩阵的一种方法是一次一层地进行.但什么是层？想想洋葱.就像洋葱的层一样,每一层被移除,我们都会向中心移动.其他类比是Matryoshka娃娃或传递包裹的游戏.
矩阵的宽度和高度决定了该矩阵中的层数.让我们为每一层使用不同的符号:
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 . . . . . . . .
您可能会注意到,将矩阵的宽度和高度递增1并不总是会增加层数.采用上述矩阵并将图层和尺寸制成表格,我们看到每两个宽度和高度增量的层数增加一次:
+-----+--------+ | N×N | Layers | +-----+--------+ | 1×1 | 1 | | 2×2 | 1 | | 3×3 | 2 | | 4×4 | 2 | | 5×5 | 3 | | 6×6 | 3 | | 7×7 | 4 | +-----+--------+
但是,并非所有图层都需要旋转.旋转前后1×1矩阵是相同的.无论整体矩阵有多大,中心1×1层在旋转前后总是相同的:
+-----+--------+------------------+ | N×N | Layers | Rotatable Layers | +-----+--------+------------------+ | 1×1 | 1 | 0 | | 2×2 | 1 | 1 | | 3×3 | 2 | 1 | | 4×4 | 2 | 2 | | 5×5 | 3 | 2 | | 6×6 | 3 | 3 | | 7×7 | 4 | 3 | +-----+--------+------------------+
给定N×N矩阵,我们如何以编程方式确定需要旋转的层数？如果我们将宽度或高度除以2并忽略余数,我们得到以下结果.
+-----+--------+------------------+---------+ | N×N | Layers | Rotatable Layers | N/2 | +-----+--------+------------------+---------+ | 1×1 | 1 | 0 | 1/2 = 0 | | 2×2 | 1 | 1 | 2/2 = 1 | | 3×3 | 2 | 1 | 3/2 = 1 | | 4×4 | 2 | 2 | 4/2 = 2 | | 5×5 | 3 | 2 | 5/2 = 2 | | 6×6 | 3 | 3 | 6/2 = 3 | | 7×7 | 4 | 3 | 7/2 = 3 | +-----+--------+------------------+---------+
请注意如何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
这是在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;
}
蟒蛇:
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)通过将列表中的相应项目堆叠到新列表中来交换2d阵列的轴.(*运算符告诉函数将包含的列表分配到参数中)
>>> 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;
}
}
这里有很多好的代码,但我只想展示几何上发生的事情,这样你就能更好地理解代码逻辑.我将如何处理这个问题.
首先,不要把这与转换混淆,这很容易..
basica的想法是将其视为图层,我们一次旋转一层.
说我们有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中更好的版本:我已经为具有不同宽度和高度的矩阵制作了它
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);有几个人已经提出了涉及制作新阵列的例子.
还有一些需要考虑的事情:
(a)不是实际移动数据,而是简单地以不同方式遍历"旋转"数组.
(b)就地轮换可能有点棘手.你需要一些划痕的地方(大概相当于一行或一列的大小).有一篇关于进行就地转置的古老ACM论文(http://doi.acm.org/10.1145/355719.355729),但他们的示例代码是讨厌的转载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
京公网安备 11010802040832号 | 京ICP备19059560号-6 