将二维数组旋转 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，层 将采用 0 到 1 之间的值，因为有 2 层，因为我们可以忽略不受旋转影响的中心元素/层。 first 和 last 指的是图层中元素的第一行和最后一行/列；例如，第 0 层包含从行/列 first = 0 到 last = 4 的元素，第 1 层包含从行/列 1 到 3 的元素。

然后对于每个层/方块，内部for(int i=first; i偏移表示我们沿着正方形边的距离。对于下面的 5x5，我们首先旋转红色元素（偏移 = 0），然后旋转黄色（偏移 = 1），然后旋转绿色和蓝色。箭头 1-5 演示了红色元素的 4 元素旋转，以及以相同方式执行的其余元素的 6+ 旋转。请注意 4 元素旋转本质上是 5 分配循环交换，其中第一个分配暂时搁置一个元素。此分配的 //save the top left of the 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);
}