将一个二维数组顺时针旋转90度

Question

我正在学习旋转NxN矩阵的代码；我已经反复追踪了程序，也有点理解实际旋转发生的方式。它基本上先按顺时针方向旋转角落，然后再旋转角落后的元素。但是还有几行代码我不理解，这段代码还没有完全被我掌握。请帮忙。 我的示例是一个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]

---

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

}

- Marie Lucy

Answer 1

如果你画一个图表，就更容易理解这样的算法，所以我在Paint中制作了一个快速图片来演示一个5x5矩阵的情况:D

外部的for(int layer=0; layer < n/2; ++layer)循环从外向内迭代各个层。外层(第0层)由有色元素表示。每一层实际上都是需要旋转的元素的正方形。对于n = 5，layer将取值0到1，因为我们可以忽略不受旋转影响的中心元素/层。 first和last指的是一层中元素的第一行/列和最后一行/列；例如，第0层的元素从行/列first = 0到last = 4，第1层从行/列1到3。

然后针对每个层/正方形，内部的for(int i=first; i<last;++i)循环通过每次旋转4个元素来旋转它。 Offset表示我们沿着正方形的边缘走多远。对于我们下面的5x5，我们首先旋转红色元素（offset = 0），然后是黄色的(offset = 1)，然后是绿色和蓝色。箭头1-5演示了红色元素的4个元素旋转，而6+则是以相同方式执行的其余元素。请注意，4个元素旋转本质上是一个5次赋值的循环交换，其中第一个赋值临时放置一个元素。对于这个赋值，注释//save the top left of the matrix是误导性的，因为matrix[first][i]不一定是矩阵的左上角，甚至不一定是该层。此外，请注意，正在旋转的元素的行/列索引有时与offset成比例，有时与其倒数成比例，即last - offset。

我们以这种方式沿着外层的边缘移动（由first=0和last=4界定），然后移动到内层（first = 1和last = 3）并在那里进行相同的操作。最终，我们到达中心，完成了整个旋转。

- asdfjklqwer

Answer 2

这会引起一个困惑。原地旋转矩阵最简单的方法是：

• 首先对矩阵进行转置（将M [i，j]与M [j，i]交换）
• 然后将M [i，j]与M [i，nColumns-j]交换

当矩阵为列主序时，第二个操作是交换列，因此具有良好的数据局部性质。如果矩阵是行主序，则首先对行进行排列，然后进行转置。

- Alexandre C.

---

我同意这是一种更简单的方法，但对于小矩阵来说效率会不会低很多呢？转置矩阵将元素移动到正确的行，但错误的列，这需要后续纠正。OP的算法在第一次操作中将元素移动到正确的行和列（总的赋值次数更少）。我在这个比较中忽略了局部性，因为对于小矩阵来说这不是问题。对于大矩阵，我们可能需要改变OP算法中的赋值顺序，并优化此算法中的转置。 - asdfjklqwer

@Nathan：两种方法执行相同数量的内存加载和内存赋值（请记住，交换临时变量通常是一个寄存器，以及OP代码中的“top”）。这个方法简单易懂，可读性强，并且可能比所提出的方法更有效，因为它不会打乱连续的数据。 - Alexandre C.

Answer 3

这是一种递归解决方案：

//将一个2D数组（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);
}

- rockhdsn