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


当前回答

我的c#示例代码的伟大算法发送@dimple:

/* Author: Dudi,
 * http://www.tutorialspoint.com/compile_csharp_online.php?PID=0Bw_CjBb95KQMYm5qU3VjVGNuZFU */

using System.IO;
using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("Rotating this matrix by 90+ degree:");

        int[,] values=new int[3,3]{{1,2,3}, {4,5,6}, {7,8,9}};
        //int[,] values=new int[4,4]{{101,102,103, 104}, {105,106, 107,108}, {109, 110, 111, 112}, {113, 114, 115, 116}};

        print2dArray(ref values);
        transpose2dArray(ref values);
        //print2dArray(ref values);
        reverse2dArray(ref values);
        Console.WriteLine("Output:");
        print2dArray(ref values);
    }

    static void print2dArray(ref int[,] matrix){
        int  nLen = matrix.GetLength(0);
        int  mLen = matrix.GetLength(1);    
        for(int n=0; n<nLen; n++){
            for(int m=0; m<mLen; m++){
                Console.Write(matrix[n,m] +"\t");
            }
            Console.WriteLine();        
        }
        Console.WriteLine();
    }

    static void transpose2dArray(ref int[,] matrix){
        int  nLen = matrix.GetLength(0);
        int  mLen = matrix.GetLength(1);    
        for(int n=0; n<nLen; n++){
            for(int m=0; m<mLen; m++){
                if(n>m){
                    int tmp = matrix[n,m];
                    matrix[n,m] = matrix[m,n];
                    matrix[m,n] = tmp;
                }
            }
        }
    }

    static void reverse2dArray(ref int[,] matrix){
        int  nLen = matrix.GetLength(0);
        int  mLen = matrix.GetLength(1);
        for(int n=0; n<nLen; n++){
            for(int m=0; m<mLen/2; m++){                
                int tmp = matrix[n,m];
                matrix[n,m] = matrix[n, mLen-1-m];
                matrix[n,mLen-1-m] = tmp;
            }
        }
    }
}

/*
Rotating this matrix by 90+ degree:                                                                                                                                             
1       2       3                                                                                                                                                               
4       5       6                                                                                                                                                               
7       8       9                                                                                                                                                               

Output:                                                                                                                                                                         
7       4       1                                                                                                                                                               
8       5       2                                                                                                                                                               
9       6       3  
*/

其他回答

下面是Java版本:

public static void rightRotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
           int offset = i - first;
           int temp = matrix[first][i];
           matrix[first][i] = matrix[last-offset][first];
           matrix[last-offset][first] = matrix[last][last-offset];
           matrix[last][last-offset] = matrix[i][last];
           matrix[i][last] = temp;
        }
    }
}

该方法首先旋转最外层,然后按顺序移动到内层。

对于i:= 0到X 对于j:= 0到X做 [j][i]:= graphic2[X-i][j]

X是图形所在数组的大小。

在Java中

public class Matrix {
/* Author Shrikant Dande */
private static void showMatrix(int[][] arr,int rows,int col){

    for(int i =0 ;i<rows;i++){
        for(int j =0 ;j<col;j++){
            System.out.print(arr[i][j]+" ");
        }
        System.out.println();
    }

}

private static void rotateMatrix(int[][] arr,int rows,int col){

    int[][] tempArr = new int[4][4];
    for(int i =0 ;i<rows;i++){
        for(int j =0 ;j<col;j++){
            tempArr[i][j] = arr[rows-1-j][i];
            System.out.print(tempArr[i][j]+" ");
        }
        System.out.println();
    }

}
public static void main(String[] args) {
    int[][] arr = { {1,  2,  3,  4},
             {5,  6,  7,  8},
             {9,  1, 2, 5},
             {7, 4, 8, 9}};
    int rows = 4,col = 4;

    showMatrix(arr, rows, col);
    System.out.println("------------------------------------------------");
    rotateMatrix(arr, rows, col);

}

}

下面是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,因为它们是相同的