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

Question

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

所以，给定一个宽度：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}

我知道如何通过创建一个新数组来做到这一点，但我想知道如何像前面提到的问题的解决方案一样就地做到这一点。

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);
        }
    }
}

Answer 2

一种方法是将原始矩阵的每个现有元素移动到其新位置，注意首先在目标索引处获取值，以便它也可以移动到新位置。对于任意 NxM 矩阵，索引 X 处元素的目标索引可以计算为：

X_new = ((N*X) / (M*N)) + ((N*X) % (M*N))

其中“/”运算符表示整数除法（商），“%”是模运算符（余数）——我在这里使用 Python 语法。

问题是，如果您从任意位置开始，则不能保证遍历矩阵中的所有元素。解决此问题的最简单方法是维护已移动到正确位置的元素的位图。

这是一些实现此目的的 Python 代码：

M = 4
N = 3
MN = M*N

X = range(0,MN)

bitmap = (1<<0) + (1<<(MN-1))
i = 0

while bitmap != ( (1<<MN) - 1):
    if (bitmap & (1<<i)):
        i += 1
        xin = X[i]
        i = ((N*i)/MN) + ((N*i) % MN)
    else:
        xout = X[i]
        X[i] = xin
        bitmap += (1<<i)
        i = ((N*i)/MN) + ((N*i) % MN)
        xin = xout

print X

为了清楚起见，我牺牲了一些优化。可以使用更复杂的算法来避免位图——如果您真的很想以计算为代价来节省内存，请查看相关Wikipedia 文章中的参考资料。