Поворот двумерного массива на 90 градусов

Question

Я изучаю этот фрагмент кода на вращении матрицы NxN; Я прослеживал программу бесчисленное количество раз, и я вроде понимаю, как происходит фактическое вращение. В основном он сначала поворачивает углы, а элементы после углов - по часовой стрелке. Я просто не понимаю пару строк, и код, так сказать, до сих пор не «загнан домой». Пожалуйста помоги. Я поворачиваю его на 90 градусов, используя в качестве примера трассировки матрицу 4x4.

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

---

public static void rotate(int[][] matrix, int n){
  for(int layer=0; layer < n/2; ++layer) {
     int first=layer; //It moves from the outside in. 
     int last=n-1-layer; //<--This I do not understand  
     for(int i=first; i<last;++i){
       int offset=i-first; //<--A bit confusing for me

       //save the top left of the matrix 
       int top = matrix[first][i];

       //shift left to top; 
       matrix[first][i]=matrix[last-offset][first]; 
       /*I understand that it needs
        last-offset so that it will go up the column in the matrix,
       and first signifies it's in the first column*/

       //shift bottom to left 
       matrix[last-offset][first]=matrix[last][last-offset];
        /*I understand that it needs
        last-offset so that the number decreases and it may go up the column (first 
        last-offset) and left (latter). */

       //shift right to bottom
       matrix[last][last-offset]=matrix[i][last];
        /*I understand that it i so that in the next iteration, it moves down 
        the column*/        



       //rightmost top corner
        matrix[i][last]=top;
       }
   }

}

Answer 1

Алгоритм, подобный этому, легче понять, если вы рисуете диаграмму, поэтому я сделал быстрый рис в Paint для демонстрации для матрицы 5x5: D

Внешний цикл for(int layer=0; layer < n/2; ++layer) перебирает слои снаружи внутрь. Внешний слой (слой 0) изображен цветными элементами. Каждый слой фактически представляет собой квадрат элементов, требующих вращения. Для n = 5, layer будет принимать значения от 0 до 1, так как есть 2 слоя, так как мы можем игнорировать центральный элемент / слой, на который не влияет вращение. first и last относятся к первым и последним строкам / столбцам элементов слоя; например слой 0 содержит элементы из строки / столбца first = 0 до last = 4 и слой 1 из строки / столбца 1 в 3.

Затем для каждого слоя / квадрата внутренний цикл for(int i=first; i<last;++i) вращает его, вращая 4 элемента в каждой итерации. Смещение показывает, как далеко мы по сторонам квадрата. Для нашего 5x5 ниже мы сначала поворачиваем красные элементы (смещение = 0), затем желтый (смещение = 1), затем зеленый и синий. Стрелки 1-5 демонстрируют 4-элементное вращение для красных элементов и 6+ для остальных, которые выполняются таким же образом. Обратите внимание, что 4-элементное вращение - это, по сути, циклический своп с 5 назначениями, при котором первое назначение временно откладывает элемент. Комментарий //save the top left of the matrix для этого назначения вводит в заблуждение, поскольку matrix [first] [i] не обязательно является верхним левым краем матрицы или даже слоем в этом отношении. Также обратите внимание, что индексы строк / столбцов вращающихся элементов иногда пропорциональны смещению , а иногда пропорциональны его обратному последнему - смещению .

Мы перемещаемся по сторонам внешнего слоя (обозначены first = 0 и last = 4) таким образом, затем переходим на внутренний слой (first = 1 и last = 3) и делаем там то же самое. В конце концов, мы попали в центр, и мы закончили.

Answer 2

Это вызывает WTF. Самый простой способ повернуть матрицу на месте - это

• сначала транспонировать матрицу (поменять местами M [i, j] с M [j, i])
• затем поменять местами M [i, j] на M [i, nColumns - j]

Когда матрицы являются основными по столбцам, вторая операция - это замена столбцов, и, следовательно, она имеет хорошие свойства локальности данных. Если матрица является основной строкой, то сначала переставьте строки, а затем транспонируйте.

Answer 3

Вот рекурсивный способ решения этой проблемы:

// поворот массива 2 D (mXn) на 90 градусов

public void rotateArray(int[][] inputArray) {
    System.out.println("Input Array: ");
    print2D(inputArray);
    rotateArray(inputArray, 0, 0, inputArray.length - 1,
            inputArray[0].length - 1);
    System.out.println("\n\nOutput Array: ");
    print2D(inputArray);

}

public void rotateArray(int[][] inputArray, int currentRow,
        int currentColumn, int lastRow, int lastColumn) {

    // condition to come out of recursion.
    // if all rows are covered or all columns are covered (all layers
    // covered)
    if (currentRow >= lastRow || currentColumn >= lastColumn)
        return;
    // rotating the corner elements first
    int top = inputArray[currentRow][currentColumn];
    inputArray[currentRow][currentColumn] = inputArray[lastRow][currentColumn];
    inputArray[lastRow][currentColumn] = inputArray[lastRow][lastColumn];
    inputArray[lastRow][lastColumn] = inputArray[currentRow][lastColumn];
    inputArray[currentRow][lastColumn] = top;

    // clockwise rotation of remaining elements in the current layer
    for (int i = currentColumn + 1; i < lastColumn; i++) {
        int temp = inputArray[currentRow][i];
        inputArray[currentRow][i] = inputArray[lastRow - i][currentColumn];
        inputArray[lastRow - i][currentColumn] = inputArray[lastRow][lastColumn
                - i];
        inputArray[lastRow][lastColumn - i] = inputArray[currentRow + i][lastColumn];
        inputArray[currentRow + i][lastColumn] = temp;
    }

    // call recursion on remaining layers
    rotateArray(inputArray, ++currentRow, ++currentColumn, --lastRow,
            --lastColumn);
}