你如何旋转二维数组？
受到Raymond Chen的文章的启发，假设你有一个4×4的二维数组，写一个旋转90度的函数。 雷蒙德链接到伪代码的解决scheme，但我希望看到一些现实世界的东西。
[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更好？ 如果matrix是10000×10000呢？
这里是在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）空间algorithm （没有任何解决方法和hanky-panky的东西！）
旋转+90：
- 颠倒
- 反转每一行
旋转-90：
方法1：
- 颠倒
- 反转每一列
方法2：
- 反转每一行
- 颠倒
旋转180°：
方法1 ：旋转+90两次
方法2 ：反转每一行，然后反转每一列（移调）
旋转-180：
方法1 ：旋转-90两次
方法2 ：反转每列，然后反转每一行
方法3 ：旋转180°，因为它们是相同的
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)将通过将列表中的相应项目堆叠到新列表中来交换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]位置变化将反转matrix的不同级别的列表。
我想补充一点细节。 在这个答案中，重要的概念是重复的，速度缓慢，故意重复。 这里提供的解决scheme不是语法上最紧凑的，但是它是为那些希望了解matrix旋转是什么的人以及最终实现的。
首先，什么是matrix？ 为了这个答案的目的，一个matrix只是一个网格的宽度和高度是相同的。 请注意，matrix的宽度和高度可能不同，但为简单起见，本教程仅考虑matrix的宽度和高度相等（是的，matrix是matrix的复数）。 示例matrix是：2×2,3×3或5×5。 或者更一般地说，N×N。 2×2matrix将有4个正方形，因为2×2 = 4。 5×5matrix将有25个正方形，因为5×5 = 25。 每个广场被称为元素或条目。 我们将在下面的图表中用句点（ . ）表示每个元素：
2×2matrix
. . . .
3×3matrix
. . . . . . . . .
4×4matrix
. . . . . . . . . . . . . . . .
那么，旋转matrix意味着什么？ 让我们采取一个2×2的matrix，并在每个元素中放置一些数字，这样就可以观察到旋转：
0 1 2 3
旋转90度给我们：
2 0 3 1
就像转动汽车的方向盘一样，我们将整个matrix按字面向右移动一次。 这可能有助于将matrix“倾倒”在其右侧。 我们想用Python编写一个函数，它需要一个matrix并向右旋转一次。 函数签名将是：
def rotate(matrix): # Algorithm goes here.
matrix将使用二维数组来定义：
matrix = [ [0,1], [2,3] ]
因此，第一个索引位置访问该行。 第二个索引位置访问列：
matrix[row][column]
我们将定义一个实用函数来打印matrix。
def print_matrix(matrix): for row in matrix: print row
旋转matrix的一种方法是一次做一层。 但是什么是层？ 想想洋葱。 就像洋葱层一样，每一层都被移走，我们移向中心。 其他类比是一个Matryoshka娃娃或通过包裹游戏。
matrix的宽度和高度决定了matrix中的层数。 我们为每个图层使用不同的符号：
2×2matrix有1层
. . . .
一个3×3matrix有2层
. . . . x . . . .
一个4×4matrix有2层
. . . . . xx . . xx . . . . .
5×5matrix有3层
. . . . . . xxx . . x O x . . xxx . . . . . .
6×6matrix有3层
. . . . . . . xxxx . . x OO x . . x OO x . . xxxx . . . . . . .
7×7matrix有4层
. . . . . . . . xxxxx . . x OOO x . . x O - O x . . x OOO x . . xxxxx . . . . . . . .
您可能会注意到，将matrix的宽度和高度递增1并不总是增加图层的数量。 采取上述matrix，并列出层和尺寸，我们看到，每增加两个宽度和高度增加一层的数量：
+-----+--------+ | 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×1matrix相同。 旋转之前和之后的中心1×1层总是相同的，不pipe整个matrix有多大：
+-----+--------+------------------+ | 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×Nmatrix，我们如何以编程方式确定我们需要旋转的层数？ 如果我们将宽度或高度除以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如何匹配需要旋转的层数？ 有时可旋转层的数量是matrix中总层数的一个。 当最内层仅由一个元件（即，1×1matrix）形成并因此不需要旋转时发生这种情况。 它只是被忽略。
我们无疑将需要这个信息在我们的函数中旋转一个matrix，所以让我们现在添加它：
def rotate(matrix): size = len(matrix) # Rotatable layers only. layer_count = size / 2
现在我们知道图层是什么以及如何确定实际需要旋转的图层数量，我们如何隔离一个图层以便旋转图层？ 首先，我们检查从最外层向内的matrix到最内层。 一个5×5的matrix共有三层，需要旋转的两层：
. . . . . . xxx . . x O x . . xxx . . . . . .
我们先看看列。 假设我们从0开始计算，定义最外层的列的位置是0和4：
+--------+-----------+ | Column | 0 1 2 3 4 | +--------+-----------+ | | . . . . . | | | . xxx . | | | . x O x . | | | . xxx . | | | . . . . . | +--------+-----------+
0和4也是最外层的行的位置。
+-----+-----------+ | Row | | +-----+-----------+ | 0 | . . . . . | | 1 | . xxx . | | 2 | . x O x . | | 3 | . xxx . | | 4 | . . . . . | +-----+-----------+
由于宽度和高度是相同的，所以总会是这种情况。 因此，我们可以用两个值（而不是四个）定义一个图层的列和行位置。
向内移动到第二层，列的位置是1和3.是的，你猜对了，行也是一样的。 理解我们必须在向内移动到下一层时增加和减less行和列的位置是很重要的。
+-----------+---------+---------+---------+ | Layer | Rows | Columns | Rotate? | +-----------+---------+---------+---------+ | Outermost | 0 and 4 | 0 and 4 | Yes | | Inner | 1 and 3 | 1 and 3 | Yes | | Innermost | 2 | 2 | No | +-----------+---------+---------+---------+
因此，为了检查每一层，我们需要一个循环，从最外层开始，增加和减less表示向内移动的计数器。 我们将这个叫做“图层循环”。
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和lastvariables标识第一个和最后一个行和列的索引位置。 回顾我们的行列表：
+--------+-----------+ | Column | 0 1 2 3 4 | +--------+-----------+ | | . . . . . | | | . xxx . | | | . x O x . | | | . xxx . | | | . . . . . | +--------+-----------+ +-----+-----------+ | Row | | +-----+-----------+ | 0 | . . . . . | | 1 | . xxx . | | 2 | . x O x . | | 3 | . xxx . | | 4 | . . . . . | +-----+-----------+
所以我们可以浏览一个matrix的图层。 现在我们需要在图层中进行导航，以便可以在该图层周围移动元素。 请注意，元素从一层到另一层都不会“跳跃”，但是它们确实在其各自的层中移动。
旋转图层中的每个元素会旋转整个图层。 旋转matrix中的所有图层会旋转整个matrix。 这句话是非常重要的，所以请在继续之前尽量理解它。
现在，我们需要一种实际移动元素的方式，即旋转每个元素，然后旋转层，最后是matrix。 为了简单，我们将恢复到一个3x3matrix – 有一个可旋转的层。
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 | +-----+-------+
因为我们的matrix总是正方形的，所以我们只需要两个variables， 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.
首先和最后的variables可以很容易地用来引用matrix的四个angular。 这是因为angular落本身可以使用first和last （没有减法，增加或偏移这些variables）的各种排列来定义：
+-----------------+-----------------+-------------+ | Corner | Position | 3x3 Values | +-----------------+-----------------+-------------+ | top left | (first, first) | (0,0) | | top right | (first, last) | (0,2) | | bottom right | (last, last) | (2,2) | | bottom left | (last, first) | (2,0) | +-----------------+-----------------+-------------+
出于这个原因，我们开始在外四个angular落的旋转 – 我们将首先旋转。 我们用*突出显示它们。
* 1 * 3 4 5 * 7 *
我们要把每个*和*右边的换成* 。 所以让我们继续打印我们的angular落定义使用只有各种排列的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)
现在我们可以很容易地从我们的图层循环中交换每个angular落：
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)
转angular前的matrix：
[0, 1, 2] [3, 4, 5] [6, 7, 8]
转angular后的matrix：
[6, 1, 0] [3, 4, 5] [8, 7, 2]
大！ 我们已经成功旋转matrix的每个angular落。 但是，我们没有在每一层的中间旋转元素。 很明显，我们需要一种在一个图层中进行迭代的方法。
问题是，到目前为止，我们的函数中唯一的循环（我们的图层循环）在每次迭代中移动到下一层。 由于我们的matrix只有一个可旋转的层，因此只有在旋转angular落后，层环才会退出。 让我们来看看更大的5×5matrix（两层需要旋转）会发生什么。 function代码已被省略，但仍与上面相同：
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]
旋转最外层的angular部不应该是一个惊喜，但是，您也可能会注意到下一层（向内）的angular也被旋转了。 这是有道理的。 我们编写了代码来浏览图层，并旋转每个图层的angular落。 这感觉就像是进步，但不幸的是我们必须退后一步。 直到前一层（外层）完全旋转后才能移动到下一层。 也就是说，直到图层中的每个元素都被旋转了。 只旋转angular落不会！
深呼吸一下。 我们需要另一个循环。 嵌套循环不下。 新的嵌套循环将使用第first和lastvariables以及一个偏移量在一个图层中进行导航。 我们将这个新的循环称为我们的“元素循环”。 元素循环将访问顶行中的每个元素，每个元素沿着右侧，每个元素沿着底行，每个元素沿着左侧。
- 沿着第一行向前移动需要增加列索引。
- 向右移动需要增加行索引。
- 沿着底部向后移动需要列索引减less。
- 向左移动需要减less行索引。
这听起来很复杂，但是这很容易实现，因为为了实现上述目的而增加和减less的次数在matrix的所有四条边上保持不变。 例如：
- 在第一行中移动1个元素。
- 向右移动1个元素。
- 沿着底行向后移动1个元素。
- 向左移动1个元素。
这意味着我们可以使用一个variables与第first和lastvariables结合在一个图层中移动。 这可能有助于指出，在顶行和右侧移动都需要递增。 在沿着底部向上和向左移动时都需要递减。
def rotate(matrix): size = len(matrix) layer_count = size / 2 # Move through layers (ie layer loop). for layer in range(0, layer_count): first = layer last = size - first - 1 # Move within a single layer (ie 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
给定matrix：
0, 1, 2 3, 4, 5 6, 7, 8
我们的rotatefunction导致：
6, 3, 0 7, 4, 1 8, 5, 2
这里是一个旋转的地方，而不是使用一个全新的数组来保存结果。 我已经放弃了数组的初始化并将其打印出来。 这只适用于方阵，但它们可以是任意大小的。 内存开销等于数组的一个元素的大小，所以你可以做任意大的数组的旋转。
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][ni-1]; a[j][ni-1] = a[ni-1][nj-1]; a[ni-1][nj-1] = a[nj-1][i]; a[nj-1][i] = tmp; } }
在这里有很多很好的代码，但是我只是想要显示几何上发生了什么，所以你可以更好地理解代码逻辑。 这是我将如何处理这个问题。
首先，不要把这个和转换很容易混淆。
基本的想法是把它作为图层，我们一次旋转一层。
说我们有一个4×4
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个angular落
1 4 13 16
然后我们旋转下面那种歪斜的钻石
2 8 9 15
然后是第二颗歪斜的钻石
3 5 12 14
所以照顾外缘，所以基本上我们一次只做一个shell
最后是中间的广场（或者如果它是奇怪的只是最后一个不动的元素）
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,ni], [i,ni] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
正如我在之前的文章中所说的，这是C＃中的一些代码，它为任意大小的matrix实现了O（1）matrix旋转。 为了简洁和易读，没有错误检查或范围检查。 代码：
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。 对构造函数做一个小小的改变来创build一个新的数组，然后将值复制到这个数组中将会把它排除。
虽然可能需要旋转数据（也许更新物理存储的表示forms），但是在arrays访问（可能是一个接口）上添加一个间接层可能会变得更简单，可能更具性能：
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中是一个更好的版本：我已经做了一个不同的宽度和高度的matrix
- h是旋转后matrix的高度
- 这里w是旋转后matrix的宽度
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的post。
Ruby-way: .transpose.map &:reverse
There are a lot of answers already, and I found two claiming O(1) time complexity. The real O(1) algorithm is to leave the array storage untouched, and change how you index its elements. The goal here is that it does not consume additional memory, nor does it require additional time to iterate the data.
Rotations of 90, -90 and 180 degrees are simple transformations which can be performed as long as you know how many rows and columns are in your 2D array; To rotate any vector by 90 degrees, swap the axes and negate the Y axis. For -90 degree, swap the axes and negate the X axis. For 180 degrees, negate both axes without swapping.
Further transformations are possible, such as mirroring horizontally and/or vertically by negating the axes independently.
This can be done through eg an accessor method. The examples below are JavaScript functions, but the concepts apply equally to all languages.
// 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 couple of people have already put up examples which involve making a new array.
A few other things to consider:
(a) Instead of actually moving the data, simply traverse the "rotated" array differently.
(b) Doing the rotation in-place can be a little trickier. You'll need a bit of scratch place (probably roughly equal to one row or column in size). There's an ancient ACM paper about doing in-place transposes ( http://doi.acm.org/10.1145/355719.355729 ), but their example code is nasty goto-laden FORTRAN.
Addendum:
http://doi.acm.org/10.1145/355611.355612 is another, supposedly superior, in-place transpose algorithm.
Nick's answer would work for an NxM array too with only a small modification (as opposed to an NxN).
string[,] orig = new string[n, m]; string[,] rot = new string[m, n]; ... for ( int i=0; i < n; i++ ) for ( int j=0; j < m; j++ ) rot[j, n - i - 1] = orig[i, j];
One way to think about this is that you have moved the center of the axis (0,0) from the top left corner to the top right corner. You're simply transposing from one to the other.
Here's my Ruby version (note the values aren't displayed the same, but it still rotates as described).
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
Time – O(N), Space – 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; } } }
here's a in-space rotate method, by java, only for square. for non-square 2d array, you will have to create new array anyway.
private void rotateInSpace(int[][] arr) { int z = arr.length; for (int i = 0; i < z / 2; i++) { for (int j = 0; j < (z / 2 + z % 2); j++) { int x = i, y = j; int temp = arr[x][y]; for (int k = 0; k < 4; k++) { int temptemp = arr[y][z - x - 1]; arr[y][z - x - 1] = temp; temp = temptemp; int tempX = y; y = z - x - 1; x = tempX; } } } }
code to rotate any size 2d array by creating new array:
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; }
Implementation of dimple's +90 pseudocode (eg transpose then reverse each row) in 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; }
You can do this in 3 easy steps :
1 )Suppose we have a matrix
1 2 3 4 5 6 7 8 9
2 )Take the transpose of the matrix
1 4 7 2 5 8 3 6 9
3 )Interchange rows to get rotated matrix
3 6 9 2 5 8 1 4 7
Java source code for this:
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); } } ?>
Here is the Java version:
public static void rightRotate(int[][] matrix, int n) { for (int layer = 0; layer < n / 2; layer++) { int first = layer; int last = n - 1 - first; for (int i = first; i < last; i++) { int offset = i - first; int temp = matrix[first][i]; matrix[first][i] = matrix[last-offset][first]; matrix[last-offset][first] = matrix[last][last-offset]; matrix[last][last-offset] = matrix[i][last]; matrix[i][last] = temp; } } }
the method first rotate the mostouter layer, then move to the inner layer squentially.
From a linear point of view, consider the matrices:
1 2 3 0 0 1 A = 4 5 6 B = 0 1 0 7 8 9 1 0 0
Now take A transpose
1 4 7 A' = 2 5 8 3 6 9
And consider the action of A' on B, or B on A'.
Respectively:
7 4 1 3 6 9 A'B = 8 5 2 BA' = 2 5 8 9 6 3 1 4 7
This is expandable for any nxn matrix. And applying this concept quickly in code:
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); } } }
C# code to rotate [n,m] 2D arrays 90 deg right
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[Xi][j]
X is the size of the array the graphic is in.
#transpose is a standard method of Ruby's Array class, thus:
% irb irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] => [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] irb(main):002:0> m.reverse.transpose => [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
The implementation is an n^2 transposition function written in C. You can see it here: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose by choosing "click to toggle source" beside "transpose".
I recall better than O(n^2) solutions, but only for specially constructed matrices (such as sparse matrices)
This is my implementation, in C, O(1) memory complexity, in place rotation, 90 degrees clockwise:
#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; } } }
C code for matrix rotation 90 degree clockwise IN PLACE for any M*N matrix
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; } } }
here is my In Place implementation in 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; } } }
Here is my attempt for matrix 90 deg rotation which is a 2 step solution in C. First transpose the matrix in place and then swap the cols.
#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; }
@dagorym: Aw, man. I had been hanging onto this as a good "I'm bored, what can I ponder" puzzle. I came up with my in-place transposition code, but got here to find yours pretty much identical to mine…ah, well. Here it is in Ruby.
require 'pp' n = 10 a = [] n.times { a << (1..n).to_a } pp a 0.upto(n/2-1) do |i| i.upto(ni-2) do |j| tmp = a[i][j] a[i][j] = a[nj-1][i] a[nj-1][i] = a[ni-1][nj-1] a[ni-1][nj-1] = a[j][ni-1] a[j][ni-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]; } }
Simple C++ method, tho there would be a big memory overhead in a big array.
