受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;
 }

其他回答

下面是一个原地旋转的数组,而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化和输出。这只适用于正方形数组,但它们可以是任何大小。内存开销等于数组中一个元素的大小,因此您可以对任意大的数组进行旋转。

int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
    for (int j = i; j < n - i - 1; j++)
    {
        tmp             = a[i][j];
        a[i][j]         = a[j][n-i-1];
        a[j][n-i-1]     = a[n-i-1][n-j-1];
        a[n-i-1][n-j-1] = a[n-j-1][i];
        a[n-j-1][i]     = tmp;
    }
}

试试我图书馆的算盘——常见的:

@Test
public void test_42519() throws Exception {
    final IntMatrix matrix = IntMatrix.range(0, 16).reshape(4);

    N.println("======= original =======================");
    matrix.println();
    // print out:
    //    [0, 1, 2, 3]
    //    [4, 5, 6, 7]
    //    [8, 9, 10, 11]
    //    [12, 13, 14, 15]

    N.println("======= rotate 90 ======================");
    matrix.rotate90().println();
    // print out:
    //    [12, 8, 4, 0]
    //    [13, 9, 5, 1]
    //    [14, 10, 6, 2]
    //    [15, 11, 7, 3]

    N.println("======= rotate 180 =====================");
    matrix.rotate180().println();
    // print out:
    //    [15, 14, 13, 12]
    //    [11, 10, 9, 8]
    //    [7, 6, 5, 4]
    //    [3, 2, 1, 0]

    N.println("======= rotate 270 ======================");
    matrix.rotate270().println();
    // print out:
    //    [3, 7, 11, 15]
    //    [2, 6, 10, 14]
    //    [1, 5, 9, 13]
    //    [0, 4, 8, 12]

    N.println("======= transpose =======================");
    matrix.transpose().println();
    // print out:
    //    [0, 4, 8, 12]
    //    [1, 5, 9, 13]
    //    [2, 6, 10, 14]
    //    [3, 7, 11, 15]

    final IntMatrix bigMatrix = IntMatrix.range(0, 10000_0000).reshape(10000);

    // It take about 2 seconds to rotate 10000 X 10000 matrix.
    Profiler.run(1, 2, 3, "sequential", () -> bigMatrix.rotate90()).printResult();

    // Want faster? Go parallel. 1 second to rotate 10000 X 10000 matrix.
    final int[][] a = bigMatrix.array();
    final int[][] c = new int[a[0].length][a.length];
    final int n = a.length;
    final int threadNum = 4;

    Profiler.run(1, 2, 3, "parallel", () -> {
        IntStream.range(0, n).parallel(threadNum).forEach(i -> {
            for (int j = 0; j < n; j++) {
                c[i][j] = a[n - j - 1][i];
            }
        });
    }).printResult();
}

这里有大量的好代码,但我只是想以几何形式展示,这样你就能更好地理解代码逻辑。以下是我的处理方法。

首先,不要把这和换位相混淆,换位是很容易的。

基本的想法是把它当作层,我们一次旋转一个层。

假设我们有一辆4x4

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

当我们顺时针旋转90度,我们得到

13  9   5   1
14  10  6   2   
15  11  7   3
16  12  8   4

我们来分解它,首先旋转这四个角

1           4


13          16

然后我们旋转下面这个有点歪斜的菱形

    2
            8
9       
        15

然后是第二个斜菱形

        3
5           
            12
    14

这就搞定了外缘基本上我们一次做一个壳层直到

最后是中间的方块(如果是奇数则是最后一个不动的元素)

6   7
10  11

现在我们来算出每一层的指标,假设我们总是在最外层工作,我们正在做

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

等等等等 直到我们走到边缘的一半

所以总的来说模式是

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

下面是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;
        }
    }
}

O(n²)时间和O(1)空间算法(没有任何变通方法和恶作剧的东西!)

旋转+90:

转置 反转每行

旋转-90:

方法一:

转置 反转每一列

方法二:

反转每行 转置

旋转180度:

方法一:旋转+90两次

方法2:反转每行,然后反转每列(转置)

旋转-180度:

方法一:旋转-90度2次

方法二:先反转每一列,再反转每一行

方法三:旋转+180,因为它们是相同的