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

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

Можно сделать рекурсивно довольно чисто, вот моя реализация в golang!

вращать матрицу nxn в go golang рекурсивно на месте без дополнительной памяти

func rot90(a [][]int) {
    n := len(a)
    if n == 1 {
        return
    }
    for i := 0; i < n; i++ {
        a[0][i], a[n-1-i][n-1] = a[n-1-i][n-1], a[0][i]
    }
    rot90(a[1:])
}

Answer 2

Для начинающих программистов, в простом 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 3

Алгоритм памяти O(1):

1. поверните самые внешние данные, тогда вы можете получить результат ниже:

   [3][9][5][1]
   [4][6][7][2]
   [5][0][1][3]
   [6][2][8][4]
   

Чтобы сделать это вращение, мы знаем

    dest[j][n-1-i] = src[i][j]

Соблюдайте ниже: a(0,0) -> a(0,3) a(0,3) -> a(3,3) a(3,3) -> a(3,0) a(3,0)) -> a(0,0)

Поэтому это круг, вы можете вращать N элементов за один цикл. Сделайте эту петлю N-1, чтобы повернуть самые внешние элементы.

1. Теперь вы можете внутреннее это тот же вопрос для 2X2.

Поэтому мы можем сделать вывод, как показано ниже:

function rotate(array, N)
{
    Rotate outer-most data
    rotate a new array with N-2 or you can do the similar action following step1
}

Answer 4

Попробуйте мою библиотеку 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();
}