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


当前回答

在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);

}

}

其他回答

这是c#的

int[,] array = new int[4,4] {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,0,1,2 },
    { 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}

为新手程序员,在纯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;
}

ruby方式:.transpose。地图&:反向

这是我对矩阵90度旋转的尝试,这是c中的2步解决方案,首先转置矩阵,然后交换cols。

#define ROWS        5
#define COLS        5

void print_matrix_b(int B[][COLS], int rows, int cols) 
{
    for (int i = 0; i <= rows; i++) {
        for (int j = 0; j <=cols; j++) {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }
}

void swap_columns(int B[][COLS], int l, int r, int rows)
{
    int tmp;
    for (int i = 0; i <= rows; i++) {
        tmp = B[i][l];
        B[i][l] = B[i][r];
        B[i][r] = tmp;
    }
}


void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
    int tmp;
    // Transpose the matrix first
    for (int i = 0; i <= rows; i++) {
        for (int j = i; j <=cols; j++) {
            tmp = B[i][j];
            B[i][j] = B[j][i];
            B[j][i] = tmp;
        }
    }
    // Swap the first and last col and continue until
    // the middle.
    for (int i = 0; i < (cols / 2); i++)
        swap_columns(B, i, cols - i, rows);
}



int _tmain(int argc, _TCHAR* argv[])
{
    int B[ROWS][COLS] = { 
                  {1, 2, 3, 4, 5}, 
                      {6, 7, 8, 9, 10},
                          {11, 12, 13, 14, 15},
                          {16, 17, 18, 19, 20},
                          {21, 22, 23, 24, 25}
                        };

    matrix_2d_rotation(B, ROWS - 1, COLS - 1);

    print_matrix_b(B, ROWS - 1, COLS -1);
    return 0;
}

这是一个如今被高估的面试问题。

我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引,然后绘制输出数组的索引。旋转前后的列分度示例如下:

30 --> 00
20 --> 01
10 --> 02
00 --> 03

31 --> 10
21 --> 11
11 --> 12
01 --> 13

注意旋转后的数字模式。

下面提供了一个简洁的Java解决方案。经过测试,它是有效的:

 Input:
    M A C P 
    B N L D 
    Y E T S 
    I W R Z 

    Output:
    I Y B M 
    W E N A 
    R T L C 
    Z S D P 

/**
 * (c) @author "G A N MOHIM"
 * Oct 3, 2015
 * RotateArrayNintyDegree.java
 */
package rotatearray;

public class RotateArrayNintyDegree {

    public char[][] rotateArrayNinetyDegree(char[][] input) {
        int k; // k is used to generate index for output array

        char[][] output = new char[input.length] [input[0].length];

        for (int i = 0; i < input.length; i++) {
            k = 0;
            for (int j = input.length-1; j >= 0; j--) {
                output[i][k] = input[j][i]; // note how i is used as column index, and j as row
                k++;
            }
        }

        return output;
    }

    public void printArray(char[][] charArray) {
        for (int i = 0; i < charArray.length; i++) {
            for (int j = 0; j < charArray[0].length; j++) {
                System.out.print(charArray[i][j] + " ");
            }
            System.out.println();
        }


    }

    public static void main(String[] args) {
        char[][] input = 
                { {'M', 'A', 'C', 'P'},
                  {'B', 'N', 'L', 'D'},
                  {'Y', 'E', 'T', 'S'},
                  {'I', 'W', 'R', 'Z'}
                };

        char[][] output = new char[input.length] [input[0].length];

        RotateArrayNintyDegree rotationObj = new RotateArrayNintyDegree();
        rotationObj.printArray(input);

        System.out.println("\n");
        output = rotationObj.rotateArrayNinetyDegree(input);
        rotationObj.printArray(output);

    }

}