将二维阵列旋转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具有来自行/列的元素首先= 0到最后= 4以及来自行/列1到3的层1.

然后对于每个图层/正方形,内部for(int i=first; i<last;++i)循环通过在每次迭代中旋转4个元素来旋转它.偏移量表示我们所在广场两侧的距离.对于我们下面的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 [j,i]交换M [i,j])
• 然后用M [i,nColumns - j]交换M [i,j]

当矩阵是列专用时,第二个操作是交换列,因此具有良好的数据局部性属性.如果矩阵是行主,那么首先置换行,然后转置.