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


当前回答

基于社区wiki算法和这个转置数组的SO答案,这里是一个Swift 4版本,可以逆时针旋转一些2D数组90度。这里假设matrix是一个2D数组:

func rotate(matrix: [[Int]]) -> [[Int]] {
    let transposedPoints = transpose(input: matrix)
    let rotatedPoints = transposedPoints.map{ Array($0.reversed()) }
    return rotatedPoints
}


fileprivate func transpose<T>(input: [[T]]) -> [[T]] {
    if input.isEmpty { return [[T]]() }
    let count = input[0].count
    var out = [[T]](repeating: [T](), count: count)
    for outer in input {
        for (index, inner) in outer.enumerated() {
            out[index].append(inner)
        }
    }

    return out
}

其他回答

JavaScript解决方案旋转矩阵90度的地方:

function rotateBy90(m) {
  var length = m.length;
  //for each layer of the matrix
  for (var first = 0; first < length >> 1; first++) {
    var last = length - 1 - first;
    for (var i = first; i < last; i++) {
      var top = m[first][i]; //store top
      m[first][i] = m[last - i][first]; //top = left
      m[last - i][first] = m[last][last - i]; //left = bottom
      m[last][last - i] = m[i][last]; //bottom = right
      m[i][last] = top; //right = top
    }
  }
  return m;
}

Javascript解决NxN矩阵与运行时O(N^2)和内存O(1)

  function rotate90(matrix){
    var length = matrix.length
    for(var row = 0; row < (length / 2); row++){
      for(var col = row; col < ( length - 1 - row); col++){
        var tmpVal = matrix[row][col];
        for(var i = 0; i < 4; i++){
          var rowSwap = col;
          var colSwap = (length - 1) - row;
          var poppedVal = matrix[rowSwap][colSwap];
          matrix[rowSwap][colSwap] = tmpVal;
          tmpVal = poppedVal;
          col = colSwap;
          row = rowSwap;
        }
      }
    }
  }

这是我的实现,在C, O(1)内存复杂度,原地旋转,顺时针90度:

#include <stdio.h>

#define M_SIZE 5

static void initMatrix();
static void printMatrix();
static void rotateMatrix();

static int m[M_SIZE][M_SIZE];

int main(void){
    initMatrix();
    printMatrix();
    rotateMatrix();
    printMatrix();

    return 0;
}

static void initMatrix(){
    int i, j;

    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            m[i][j] = M_SIZE*i + j + 1;
        }
    }
}

static void printMatrix(){
    int i, j;

    printf("Matrix\n");
    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            printf("%02d ", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

static void rotateMatrix(){
    int r, c;

    for(r = 0; r < M_SIZE/2; r++){
        for(c = r; c < M_SIZE - r - 1; c++){
            int tmp = m[r][c];

            m[r][c] = m[M_SIZE - c - 1][r];
            m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
            m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
            m[c][M_SIZE - r - 1] = tmp;
        }
    }
}

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

从线性的角度来看,考虑以下矩阵:

    1 2 3        0 0 1
A = 4 5 6    B = 0 1 0
    7 8 9        1 0 0

现在求A

     1 4 7
A' = 2 5 8
     3 6 9

考虑A'对B的作用,或B对A'的作用。 分别为:

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
      9 6 3          1 4 7

这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:

void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
    mat[r1][c1] ^= mat[r2][c2];
    mat[r2][c2] ^= mat[r1][c1];
    mat[r1][c1] ^= mat[r2][c2];
}

void transpose(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = (i + 1); j < size; j++)
        {
            swapInSpace(mat, i, j, j, i);
        }
    }
}

void rotate(int** mat, int size)
{
    //Get transpose
    transpose(mat, size);

    //Swap columns
    for (int i = 0; i < size / 2; i++)
    {
        for (int j = 0; j < size; j++)
        {
            swapInSpace(mat, i, j, size - (i + 1), j);
        }
    }
}