受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呢?
当前回答
这是一个Javascript解决方案:
const transpose = m => m[0].map((x,i) => m.map(x => x[i]));
a: // original matrix
123
456
789
transpose(a).reverse(); // rotate 90 degrees counter clockwise
369
258
147
transpose(a.slice().reverse()); // rotate 90 degrees clockwise
741
852
963
transpose(transpose(a.slice().reverse()).slice().reverse())
// rotate 180 degrees
987
654
321
其他回答
ruby方式:.transpose。地图&:反向
原地旋转不可能比O(n²)更快,原因是如果我们想旋转矩阵,我们必须至少一次触及所有n²元素,无论你实现什么算法。
为新手程序员,在纯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;
}
我的旋转版本:
void rotate_matrix(int *matrix, int size)
{
int result[size*size];
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
result[(size - 1 - i) + j*size] = matrix[i*size+j];
for (int i = 0; i < size*size; ++i)
matrix[i] = result[i];
}
在其中,我们将最后一列改为第一行,以此类推。这可能不是最理想的,但对于理解来说是清楚的。
从线性的角度来看,考虑以下矩阵:
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
这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:
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);
}
}
}