将一个二维数组顺时针旋转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？首先，偏移量是什么？

如果有人能解释这个算法的起源并带领我通过思考过程找出解决方案，那就太好了。

谢谢

- sc_ray

---

只需在调试器中运行它或打印中间结果即可。 - Dr. belisarius

Answer 1

这个想法是将大任务（旋转一个正方形矩阵）分解为更小的任务。

首先，正方形矩阵可以分成同心方形环。每个环的旋转与其他环的旋转无关，因此要旋转矩阵，只需逐个旋转每个环。在这种情况下，我们从最外面的环开始向内工作。我们使用“层”（或“第一”，相同的东西）来计数环，并在到达中间时停止，这就是为什么它上升到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}。

- Beta

---

“（或 first，同样的东西）”这个注释可能会令人困惑——layer和first在数值上始终相同，但在概念上它们是不同的。Layer用于计算我们处于哪个同心圆环中，而first和last则跟踪每条边的起点和终点。 - Jander

感谢您详细的回答。因此，当经验丰富的算法专家得到最后一个 = n-1-layer 和偏移量为 i-first 时，他们只是观察基于环行走的模式吗？我的问题可能有点奇怪，但我想要的是如何根据2D数组的特性得出n-1层和i-first表达式的思路。我想捕捉解决此类问题的思维过程，其中一些您在回答中已经很好地阐述了。 - sc_ray

@sc_ray：方法是将问题分解为更简单的问题；结果是交换四个点并在正方形上进行迭代。一种遍历正方形的方法是通过环，而一种遍历环的方法是使用“n-1层”和“i第一次”。如果这不清楚，我建议先尝试一个更简单的问题，比如逐个迭代矩形或三角形的点（而不是四个点）。 - Beta