受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]
更新:Nick的答案是最直接的,但是有没有比n²更好的方法呢?如果矩阵是10000x10000呢?
受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]
更新:Nick的答案是最直接的,但是有没有比n²更好的方法呢?如果矩阵是10000x10000呢?
当前回答
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++;
}
}
}
其他回答
一些人已经举了一些例子,其中涉及到创建一个新数组。
还有一些需要考虑的事情:
(a)不实际移动数据,只需以不同的方式遍历“旋转”的数组。
(b)就地轮换可能有点棘手。您需要一点空白的地方(大概相当于一行或一列的大小)。有一篇古老的ACM论文是关于进行原地转置的(http://doi.acm.org/10.1145/355719.355729),但是他们的示例代码是令人讨厌的充满goto的FORTRAN。
附录:
http://doi.acm.org/10.1145/355611.355612是另一种更优越的就地转置算法。
当前所有的解决方案都有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]);
}
免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!
Nick的答案也适用于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)的中心从左上角移动到右上角。你只是简单地从一个转置到另一个。
为新手程序员,在纯c++。(宝蓝的东西)
#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;
}
在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;
}