Поверните 2D-массив на месте, не используя новый массив - лучшее решение на С++?

Один из моих учеников спросил меня о такой домашней работе с массивами С++. Мне это показалось довольно интересным, поэтому, хотя я решил эту проблему, я хотел поделиться с вами своим решением и узнать другие варианты и мнения. Проблема следующая:

Проблема Дана двумерная динамическая квадратичная матрица (массив) A (nxn). Требуется повернуть массив на 90 градусов против часовой стрелки, т.е. После вращения. В поле [1,1] должно содержаться значение поля A [1, n] и A [1, n], которое должно содержать значение Анна]. И также требуется, чтобы при решении этой проблемы вы не должны использовать какой-либо другой массив.

Мое решение Я сказал студенту сделать следующее (будет представлять шаги схематически):
Я предложил определить класс, который, как его член, будет иметь 2D-массив. И для определения операции, которая будет возвращать ссылку на элемент A [j, n + 1-i], когда пользователь запросит A [i, j] один. В двух словах я предложил создать оболочку для массива и манипулировать массивом через оболочку.

Ответы

Ответ 1

В Википедии есть статья о транспозиции места на месте.

Рассмотрим:

a b c
e f g
x y z

transpose:
a e x
b f y
c g z

rotated 90 deg CCW:
c g z
b f y
a e x

Итак, после того, как у вас есть транспонирование, переверните строки, которые вы можете легко сделать на месте.

Ответ 2

Вы можете использовать "четырехстороннюю замену" и вложенный цикл с некоторой магией вращения (разработанной на бумаге):

template <typename T>
void swap(T& a, T& b, T& c, T& d)
{
    T x(a);
    a = b;
    b = c;
    c = d;
    d = x;
}

template <typename T, size_t dim>
void rotate(T (&matrix)[dim][dim])
{
    const size_t d = dim-1;
    for (size_t y = 0; y < dim/2; ++y)
    {
        for (size_t x = y; x < d-y; ++x)
        {
            swap(matrix[y  ][x  ],
                 matrix[x  ][d-y],
                 matrix[d-y][d-x],
                 matrix[d-x][y  ]);
        }
    }
}

Программа тестирования:

template <typename T, size_t dim>
void print(T (&matrix)[dim][dim])
{
    for (size_t y = 0; y < dim; ++y)
    {
        for (size_t x = 0; x < dim; ++x)
        {
            std::cout << matrix[y][x] << ' ';
        }
        std::cout << '\n';
    }
}

int main()
{
    int matrix[4][4] = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
    rotate(matrix);
    print(matrix);
}

Вывод:

Теперь вам просто нужно преобразовать это из шаблона-формы в dynamic-form;)

Ответ 3

Ну, это не С++, а Java. Извините за это, но вот рекурсивный алгоритм внутри простого массива, поддерживаемого Matrix:

public void rotateInPlaceRecursive() {
    if( rowCount != colCount ) {
        throw new IllegalStateException("Matrix must be square");
    }
    doRotateInPlaceRecursive(0);
}

public void doRotateInPlaceRecursive(int shrink) {
    if( shrink == rowCount/2 ) {
        return;
    }
    for (int col = shrink; col < colCount-shrink-1; col++) {
        int row = shrink;
        int top     = tab[row][col];
        int left    = tab[rowCount-col-1][row];
        int bottom  = tab[rowCount-row-1][rowCount-col-1];
        int right   = tab[col][rowCount-row-1];

        tab[row][col] = right;
        tab[rowCount-col-1][row] = top;
        tab[rowCount-row-1][rowCount-col-1] = left;
        tab[col][rowCount-row-1] = bottom;

    }
    doRotateInPlaceRecursive(shrink+1);
}

---- TEST

@Test
public void testRotateInPlaceRecursive() {
    // given
    int N = 5;
    Matrix matrix = new Matrix(N, N);

    // when
    int i=0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            matrix.set(row,col, i++ );
        }
    }

    // then
    matrix.rotateInPlaceRecursive();
    i = 0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            assertEquals(i++,matrix.get(N-col-1,row));
        }
    }
}

Ответ 4

Ниже приведен пример Java и его легко можно использовать для С++. Вращение больших матриц в памяти может потреблять много ресурсов, особенно когда значения матрицы являются сложными объектами. В таких случаях может быть более эффективным пересчет индексов с функциями, которые перенаправляют их на элементы повернутой матрицы без фактического вращения.

public class RotateArray {

public static char arr[][] = { { 'a', 'b', 'c','1' }, { 'd', 'e', 'f','2' }, { 'g', 'h', 'i','3' },{ 'j', 'k', 'l','4' } };
private static int imax = arr.length-1;
private static int jmax = arr[0].length-1;

public static void printArray() {

    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[i][j] + " ");
        }
        System.out.print("\n");
    }
}

public static void printRotatedArray() {
    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[getRotatedI(i,j)][getRotatedJ(i,j)] + " ");
        }
        System.out.print("\n");
    }
}   

public static int getRotatedI(int i,int j){     
    int ii = imax-j;
    return ii;
}

public static int getRotatedJ(int i,int j){
    int jj = i;
    return jj;
}       

public static void main(String[] args) {

    System.out.println("Printing matrix");
    printArray();
    System.out.println("Printing rotated matrix");
    printRotatedArray();
}

}

Вывод:

Printing matrix
a b c 1 
d e f 2 
g h i 3 
j k l 4 

Printing rotated matrix
j g d a 
k h e b 
l i f c 
4 3 2 1

Ответ 5

O (n ^ 2) и O (1) пространственный алгоритм (без каких-либо обходных решений и hanky-panky!)

Повернуть на +90:

Transpose
Reverse each row

Повернуть на -90:

Transpose
Reverse each column

Повернуть на +180:

Способ 1: Повернуть на +90 дважды

Способ 2: Обратить каждую строку, а затем отменить каждый столбец

Повернуть на -180:

Способ 1: Повернуть на -90 дважды

Способ 2: Обратить внимание на каждый столбец и затем отменить каждую строку

Метод 3: Обратный на +180, поскольку они одинаковы