如何旋转二维数组？
时间：2020-03-05 18:47:17 来源:igfitidea点击:
受雷蒙德·陈(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，该怎么办？
解决方案
回答
这是在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;
}
回答
这是我的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
回答
尼克的答案同样适用于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)从左上角移到了右上角。我们只是从一个移到另一个。
回答
几个人已经提出了涉及制作新阵列的示例。
需要考虑的其他一些事项：
(a)不必实际移动数据，只需以不同的方式遍历"旋转"数组即可。
(b)就地进行旋转可能会有些棘手。我们将需要一些暂存位置(可能大约等于一行或者一列的大小)。有一篇古老的ACM文章关于进行原位转置(http://doi.acm.org/10.1145/355719.355729)，但是他们的示例代码是讨厌的goto-laden FORTRAN。
附录：
http://doi.acm.org/10.1145/355611.355612是另一种据说是高级的原位转置算法。
回答
就像我在上一篇文章中所说的那样，这是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. 只需对构造函数进行一些小的更改，以创建一个新数组并将其值复制到该数组即可将其整理出来。
回答
这是一个进行适当旋转的方法，而不是使用全新的数组保存结果。我放弃了数组的初始化并打印出来。这仅适用于正方形阵列，但它们可以是任何大小。内存开销等于该数组一个元素的大小，因此我们可以根据需要旋转一个较大的数组。
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;
}
}
回答
@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
回答
虽然可能有必要旋转数据(也许更新物理存储的表示形式)，但是将一个间接层添加到数组访问(可能是一个接口)变得更简单，而且性能可能更高：
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)调用所取代。这是一个虚拟方法调用，比直接访问数组要慢，因此它取决于旋转后使用旋转数组的频率。如果只使用一次，那么这种方法肯定会成功。如果旋转，然后在长时间运行的系统中使用了几天，则原地旋转可能会更好。这也取决于我们是否可以接受前期费用。
与所有性能问题一样，衡量，衡量，衡量！
回答
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]的位置更改将颠倒矩阵不同级别中的列表。
回答
#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];
}
}
回答
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 ++方法，如果在大数组中会有很大的内存开销。
回答
这是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的帖子。
回答
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);
}
}
?>
回答
当前所有的解决方案都具有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]);
}
免责声明：我实际上没有对此进行测试。让我们玩个小虫子吧！
回答
Ruby方式：.transpose.map＆：reverse
