受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呢?
当前回答
在原地顺时针90度旋转使用矢量矢量..
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//Rotate a Matrix by 90 degrees
void rotateMatrix(vector<vector<int> > &matrix){
int n=matrix.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n;i++){
reverse(matrix[i].begin(),matrix[i].end());
}
}
int main(){
int n;
cout<<"enter the size of the matrix:"<<endl;
while (cin >> n) {
vector< vector<int> > m;
cout<<"enter the elements"<<endl;
for (int i = 0; i < n; i++) {
m.push_back(vector<int>(n));
for (int j = 0; j < n; j++)
scanf("%d", &m[i][j]);
}
cout<<"the rotated matrix is:"<<endl;
rotateMatrix(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << m[i][j] << ' ';
cout << endl;
}
}
return 0;
}
其他回答
下面是我的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
下面是Java语言:
public static void rotateInPlace(int[][] m) {
for(int layer = 0; layer < m.length/2; layer++){
int first = layer;
int last = m.length - 1 - first;
for(int i = first; i < last; i ++){
int offset = i - first;
int top = m[first][i];
m[first][i] = m[last - offset][first];
m[last - offset][first] = m[last][last - offset];
m[last][last - offset] = m[i][last];
m[i][last] = top;
}
}
}
从线性的角度来看,考虑以下矩阵:
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);
}
}
}
可以做递归相当干净,这里是我的实现在golang!
在没有额外内存的情况下递归地旋转go golang中的NXN矩阵
func rot90(a [][]int) {
n := len(a)
if n == 1 {
return
}
for i := 0; i < n; i++ {
a[0][i], a[n-1-i][n-1] = a[n-1-i][n-1], a[0][i]
}
rot90(a[1:])
}
为新手程序员,在纯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;
}