arrays - "rotate"(循环移位)二维数组的好方法是什么？

Question

这确实是一个概念性(与语言无关)问题，但为了解释起见，我将使用 C++。我更喜欢一个可以移植到其他语言的答案(没有指针算术或内存技巧)。

---

假设我们有:

• arr，我们的任意类型T的矩形二维数组T
• void shift(int dx, int dy)，执行“旋转”的函数
• numRows，行数
• numCols，列数

shift() 移动数组，使所有行都向下移动 dx 个位置，超出范围的行将回绕到开头。 (对于列和dy也是如此。)假设这就是我们的数组最初的样子:

{{a1, a2, a3, a4},
 {b1, b2, b3, b4},
 {c1, c2, c3, c4},
 {d1, d2, d3, d4}};

调用函数后:shift(2,1)，arr 应如下所示:

{{c4, c1, c2, c3},
 {d4, d1, d2, d3},
 {a4, a1, a2, a3},
 {b4, b1, b2, b3}};

在本例中，dx 为 2，因此所有内容都向下移动了两个位置，dy 为 < strong>1，所以所有东西也都移到了右边一处。

这是我解决这个问题的方法:

void shift(int dx, int dy)
{
   T newArr[numRows][numCols];
   for(int r = 0; r < numRows; r++)
   {
      for(int c = 0; c < numCols; c++)
         newArr[(r + dx) % numRows][(c + dy) % numCols] = arr[r][c];
   }
   for(int r = 0; r < numRows; r++)
   {
      for(int c = 0; c < numCols; c++)
         arr[r][c] = newArr[r][c];
   }
}

我对这段代码不满意，因为它既不节省时间，也不节省空间。我正在寻找一种更优雅的解决方案，可以用更少的循环完成更多任务，并且使用更少的内存。

Answer 1

另一种可能性是根本不移动元素。这个想法是有一个函数来转换所使用的索引，使原始数组出现旋转。

通过将原始数组包装在适当的数据类型中，性能会受到轻微影响。但每当你旋转(或镜像，或反向，或其他什么)时，你都会获得内存和时间。