Как вы вращаете двумерный массив?

Question

Вдохновленный Пост Раймонда Чена , скажем, у вас есть двумерный массив 4x4, напишите функцию, которая поворачивает его на 90 градусов. Раймонд ссылается на решение в псевдокоде, но я хотел бы увидеть некоторые реальные вещи.

[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]

Обновление : ответ Ника самый простой, но есть ли способ сделать это лучше, чем n ^ 2? Что, если матрица была 10000x10000?

Answer 1

PHP Solution для по часовой стрелке и против часовой стрелки

$aMatrix = array(
    array( 1, 2, 3 ),
    array( 4, 5, 6 ),
    array( 7, 8, 9 )
    );

function CounterClockwise( $aMatrix )
{
    $iCount  = count( $aMatrix );
    $aReturn = array();
    for( $y = 0; $y < $iCount; ++$y )
    {
        for( $x = 0; $x < $iCount; ++$x )
        {
            $aReturn[ $iCount - $x - 1 ][ $y ] = $aMatrix[ $y ][ $x ];
        }
    }
    return $aReturn;
}

function Clockwise( $aMatrix )
{
    $iCount  = count( $aMatrix );
    $aReturn = array();
    for( $y = 0; $y < $iCount; ++$y )
    {
        for( $x = 0; $x < $iCount; ++$x )
        {
            $aReturn[ $x ][ $iCount - $y - 1 ] = $aMatrix[ $y ][ $x ];
        }
    }
    return $aReturn;
}

function printMatrix( $aMatrix )
{
    $iCount = count( $aMatrix );
    for( $x = 0; $x < $iCount; ++$x )
    {
        for( $y = 0; $y < $iCount; ++$y )
        {
            echo $aMatrix[ $x ][ $y ];
            echo " ";
        }
        echo "\n";
    }
}
printMatrix( $aMatrix );
echo "\n";
$aNewMatrix = CounterClockwise( $aMatrix );
printMatrix( $aNewMatrix );
echo "\n";
$aNewMatrix = Clockwise( $aMatrix );
printMatrix( $aNewMatrix );

Answer 2

Хорошие ответы, но для тех, кто ищет для этого СУХОЙ JavaScript-код - +90 градусов и -90 градусов:

          // Input: 1 2 3
          //        4 5 6
          //        7 8 9

          // Transpose: 
          //       1 4 7
          //       2 5 8
          //       3 6 9

          // Output: 
          // +90 Degree:
          //       7 4 1
          //       8 5 2
          //       9 6 3

          // -90 Degree:
          //      3 6 9
          //      2 5 8
          //      1 4 7

          // Rotate +90
         function rotate90(matrix) {

           matrix = transpose(matrix);
           matrix.map(function(array) {
             array.reverse();
           });

           return matrix;
         }

          // Rotate -90
         function counterRotate90(matrix) {
           var result = createEmptyMatrix(matrix.length);
           matrix = transpose(matrix);
           var counter = 0;

           for (var i = matrix.length - 1; i >= 0; i--) {
             result[counter] = matrix[i];
             counter++;
           }

           return result;
         }

          // Create empty matrix
         function createEmptyMatrix(len) {
           var result = new Array();
           for (var i = 0; i < len; i++) {
             result.push([]);
           }
           return result;
         }

          // Transpose the matrix
         function transpose(matrix) {
           // make empty array
           var len = matrix.length;
           var result = createEmptyMatrix(len);

           for (var i = 0; i < matrix.length; i++) {
             for (var j = 0; j < matrix[i].length; j++) {
               var temp = matrix[i][j];
               result[j][i] = temp;
             }
           }
           return result;
         }



          // Test Cases
         var array1 = [
           [1, 2],
           [3, 4]
         ];
         var array2 = [
           [1, 2, 3],
           [4, 5, 6],
           [7, 8, 9]
         ];
         var array3 = [
           [1, 2, 3, 4],
           [5, 6, 7, 8],
           [9, 10, 11, 12],
           [13, 14, 15, 16]
         ];

          // +90 degress Rotation Tests

         var test1 = rotate90(array1);
         var test2 = rotate90(array2);
         var test3 = rotate90(array3);
         console.log(test1);
         console.log(test2);
         console.log(test3);

          // -90 degress Rotation Tests
         var test1 = counterRotate90(array1);
         var test2 = counterRotate90(array2);
         var test3 = counterRotate90(array3);
         console.log(test1);
         console.log(test2);
         console.log(test3);

Answer 3

@ Дагорым: Ой, чувак. Я держался за это как хорошую головоломку «мне скучно, что я могу обдумать». Я придумал свой код транспонирования на месте, но попал сюда, чтобы найти ваш, в значительной степени идентичный моему ... ах, хорошо. Вот это в Ruby.

require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }

pp a

0.upto(n/2-1) do |i|
  i.upto(n-i-2) do |j|
    tmp             = a[i][j]
    a[i][j]         = a[n-j-1][i]
    a[n-j-1][i]     = a[n-i-1][n-j-1]
    a[n-i-1][n-j-1] = a[j][n-i-1]
    a[j][n-i-1]     = tmp
  end
end

pp a

Answer 4

Решение 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;
        }
      }
    }
  }

Answer 5

Вот это на 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;
        }
    }
}

Answer 6

Для начинающих программистов, на простом C ++. (Borland вещи)

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

Answer 7

Попробуйте мою библиотеку AbacusUtil :

@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();
}

Answer 8

на 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);

}

}

Answer 9

Вот статический обобщенный метод C #, который сделает всю работу за вас. Переменные имеют правильное имя, поэтому вы можете легко уловить идею алгоритма.

private static T[,] Rotate180 <T> (T[,] matrix)
{
    var height = matrix.GetLength (0);
    var width = matrix.GetLength (1);
    var answer = new T[height, width];

    for (int y = 0; y < height / 2; y++)
    {
        int topY = y;
        int bottomY = height - 1 - y;
        for (int topX = 0; topX < width; topX++)
        {
            var bottomX = width - topX - 1;
            answer[topY, topX] = matrix[bottomY, bottomX];
            answer[bottomY, bottomX] = matrix[topY, topX];
        }
    }

    if (height % 2 == 0)
        return answer;

    var centerY = height / 2;
    for (int leftX = 0; leftX < Mathf.CeilToInt(width / 2f); leftX++)
    {
        var rightX = width - 1 - leftX;
        answer[centerY, leftX] = matrix[centerY, rightX];
        answer[centerY, rightX] = matrix[centerY, leftX];
    }

    return answer;
}

Answer 10

Невозможно сделать это быстрее, чем O (n ^ 2) для вращения на месте, по той причине, что если мы хотим повернуть матрицу, мы должны коснуться всех элементов n ^ 2 хотя бы один раз, нет независимо от того, какой алгоритм вы реализуете.