arrays - 将二维数组旋转 90 度

Question

在数组操作练习中出现的一个常见问题是将二维数组旋转 90 度。有一些 SO 帖子回答了如何使用各种编程语言来做到这一点。我的问题是澄清其中一个答案，并探索需要什么样的思维过程才能有机地找到答案。

我找到的这个问题的解决方案如下:

public static void rotate(int[][] matrix,int n)
{
  for( layer = 0;layer < n/2;++layer){
      int first = layer;
      int last = n -1 - layer;
      for(int i = first;i<last;++i){
        int offset = i - first;
        int top = matrix[first][i];
        matrix[first][i] = matrix[last-offset][first];
        matrix[last-offset][first] = matrix[last][last-offset];
        matrix[last][last-offset] = matrix[i][last];
        matrix[i][last] = top;
       }
    }
}

我有点了解上面的代码试图做什么，它通过进行四向交换来交换四肢/角落，并对由一些偏移分隔的其他单元格执行相同的操作。

单步执行此代码我知道它有效，但我没有得到上述给定算法的数学基础。 “层”、“第一个”、“最后一个”和偏移量背后的基本原理是什么？

“last”怎么变成了n-1-layer？为什么偏移量i-first？首先偏移量是多少？

如果有人能解释这个算法的起源并引导我完成思考过程以得出解决方案，那就太好了。

谢谢

Answer 1

这个想法是将大任务(旋转方阵)分解成更小的任务。

首先，方阵可以分解成同心方环。一个环的旋转独立于其他环的旋转，因此要旋转矩阵只需一个接一个地旋转每个环。在这种情况下，我们从最外圈开始向内工作。我们使用 layer 计算环数(或 first ，同样的事情)，当我们到达中间时停止，这就是它上升到 n/2 的原因. (值得检查以确保这适用于奇数和偶数 n 。)使用 last = n - 1 - layer 跟踪环的“远边缘”很有用。 .例如，在 5x5 矩阵中，第一个环从 first=0 开始。结束于 last=4 , 第二个环开始于 first=1结束于 last=3等等。

如何旋转环？沿着顶部边缘向右走，沿着左侧边缘向上走，沿着底部边缘向左走，沿着右侧边缘向下走，全部同时进行。在每一步交换四个值。变化的坐标是i , 步数为 offset .例如，绕二环走时，i去{1,2,3}和offset去 {0,1,2}。