将二维数组旋转 90 度
在数组操作练习中经常出现的一个问题是将二维数组旋转 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;
}
}
}
我对上面的代码试图做什么有所了解，它是通过进行四向交换来交换四肢/角并对其他单元格执行相同的操作由一些偏移量分开。
单步执行这段代码我知道它是有效的，但我没有得到的是上述算法的数学基础。 “层”、“第一层”、“最后一层”和偏移量背后的基本原理是什么？
“最后”怎么会变成n-1-layer？为什么偏移量是i-first？首先偏移量是多少？
如果有人可以解释这个算法的起源并引导我完成思考过程以提出解决方案，那就太好了。
谢谢
A frequent question that props up during array manipulation exercises is to rotate a two dimensional array by 90 degrees. There are a few SO posts that answer how to do it in a variety of programming languages. My question is to clarify one of the answers that is out there and explore what sort of thought-process is required in order to get to the answer in an organic manner.
The solution to this problem that I found goes as follows:
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;
}
}
}
I have somewhat of an idea what the code above is trying to do, it is swapping out the extremities/corners by doing a four-way swap and doing the same for the other cells separated by some offset.
Stepping through this code I know it works, what I do not get is the mathematical basis for the above given algorithm. What is the rationale behind the 'layer','first','last' and the offset?
How did 'last' turn out to be n-1-layer? Why is the offset i-first? What is the offset in the first place?
If somebody could explain the genesis of this algorithm and step me through the thought process to come up with the solution, that will be great.
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这个想法是将大任务（旋转方阵）分解为更小的任务。
首先，方阵可以分解为同心方环。一个环的旋转独立于其他环的旋转，因此旋转矩阵只需逐个旋转每个环即可。在这种情况下，我们从最外层的环开始并向内工作。我们使用
layer（或first，同样的事情）来计算环数，并在到达中间时停止，这就是为什么它上升到n/2。 （值得检查以确保这适用于奇数和偶数n。）使用last = n - 1 跟踪环的“远边缘”非常有用- 层。例如，在 5x5 矩阵中，第一个环从first=0开始，到last=4结束，第二个环从first=1开始code> 并以last=3结束，依此类推。如何旋转戒指？沿着顶部边缘向右走，沿着左侧边缘向上走，沿着底部边缘向左走，然后沿着右侧边缘向下走，全部同时进行。在每一步交换四个值。改变的坐标是
i，步数是offset。例如，当绕第二个环行走时，i变为 {1,2,3}，offset变为 {0,1,2}。The idea is to break down the big task (rotating a square matrix) into smaller tasks.
First, a square matrix can be broken into concentric square rings. The rotation of a ring is independent from the rotation of other rings, so to rotate the matrix just rotate each of the rings, one by one. In this case, we start at the outermost ring and work inward. We count the rings using
layer(orfirst, same thing), and stop when we get to the middle, which is why it goes up ton/2. (It is worth checking to make sure this will work for odd and evenn.) It is useful to keep track of the "far edge" of the ring, usinglast = n - 1 - layer. For instance, in a 5x5 matrix, the first ring starts atfirst=0and ends atlast=4, the second ring starts atfirst=1and ends atlast=3and so on.How to rotate a ring? Walk right along the top edge, up along the left edge, left along the bottom edge and down along the right edge, all at the same time. At each step swap the four values around. The coordinate that changes is
i, and the number of steps isoffset. For example, when walking around the second ring,igoes {1,2,3} andoffsetgoes {0,1,2}.