受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;
}
其他回答
这是我在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;
}
}
}
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)的中心从左上角移动到右上角。你只是简单地从一个转置到另一个。
O(1)内存算法:
旋转最外层的数据，然后你可以得到以下结果: [3] [9] [5] [1] [4] [6] [7] [2] [5] [0] [1] [3] [6] [2] [8] [4]
做这个旋转，我们知道
dest[j][n-1-i] = src[i][j]
观察下图: A (0,0) -> A (0,3) A (0,3) -> A (3,3) A (3,3) -> A (3,0) A (3,0) -> A (0,0)
因此它是一个圆，你可以在一个循环中旋转N个元素。做这个N-1循环，然后你可以旋转最外层的元素。
对于2X2，内部也是一样的问题。
因此，我们可以得出如下结论:
function rotate(array, N)
{
Rotate outer-most data
rotate a new array with N-2 or you can do the similar action following step1
}
ruby方式:.transpose。地图&:反向
private static int[][] rotate(int[][] matrix, int n) {
int[][] rotated = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotated[i][j] = matrix[n-j-1][i];
}
}
return rotated;
}
