arrays - 转置一个不代表正方形的一维数组

Question

这个问题类似于this ，但我需要转置一个矩形数组，而不是表示正方形的数组。

因此，给定宽度:x 和高度:y，我的数组有 x*y 个元素。

如果宽度为 4，高度为 3，我有:

{0,1,2,3,4,5,6,7,8,9,10,11}

代表矩阵:

0 1 2  3
4 5 6  7
8 9 10 11

我愿意:

{0,4,8,1,5,9,2,6,10,3,7,11}

我知道如何通过制作一个新数组来做到这一点，但我想知道如何像 previously mentioned question 的解决方案一样就地完成它.

Answer 1

原地转置的一种简单方法是将每个元素从矩阵的背面开始旋转到位。您一次只需要将一个元素旋转到位，例如，从 [0,1,2,3,4,5,6,7,8,9,a,b]，你得到:

0,1,2,3,4,5,6,7,8,9,a,b, // step 0
                     ,b, // step 1
             ,8,9,a,7,   // step 2
      4,5,6,8,9,a,3,     // step 3
               ,a,       // step 4
         ,8,9,6,         // step 5
   ,4,5,8,9,2,           // step 6
         ,9,             // step 7
     ,8,5,               // step 8
 ,4,8,1,                 // step 9
   ,8,                   // step 10
 ,4,                     // step 11
0,                       // step 12

(这只是显示元素在每一步中旋转到它们的最终位置。)

如果你写出每个元素要旋转多少个元素(从后到前)，它会形成一个很好的进展。例如 (width= 4, height= 3):

1,4,7,1,3,5,1,2,3,1,1,1

或者，以稍微更好的结构化方式:

1,4,7,
1,3,5,
1,2,3,
1,1,1

1 个元素的旋转实际上是无操作，但进展导致一个非常简单的算法(在 C++ 中):

void transpose(int *matrix, int width, int height)
{
    int count= width*height;

    for (int x= 0; x<width; ++x)
    {
        int count_adjustment= width - x - 1;

        for (int y= 0, step= 1; y<height; ++y, step+= count_adjustment)
        {
            int last= count - (y+x*height);
            int first= last - step;

            std::rotate(matrix + first, matrix + first + 1, matrix + last);
        }
    }
}