受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呢?


当前回答

#!/usr/bin/env python

original = [ [1,2,3],
             [4,5,6],
             [7,8,9] ]

# Rotate matrix 90 degrees...
for i in map(None,*original[::-1]):
    print str(i) + '\n'

这导致双方旋转90度(即。123(上面)现在是741(左边)。

这个Python解决方案是可行的,因为它使用了带负步的切片来反转行顺序(将7移到最上面)

original = [ [7,8,9],
             [4,5,6],
             [1,2,3] ]

然后,它使用map(以及隐含的标识函数,这是map以None作为第一个参数的结果)和*按顺序解包所有元素,重新组合列(即。第一个元素一起放在一个元组中,第二个元素一起放在一个元组中,以此类推)。你有效地得到得到返回如下重组:

original = [[7,8,9],
             [4,5,6],
             [1,2,3]]

其他回答

当前所有的解决方案都有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]);
}

免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!

在原地顺时针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;
 }

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版本(注意,值显示的不一样,但它仍然按照描述旋转)。

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