将一个不表示正方形的一维数组原地转置

Question

将一个不表示正方形的一维数组原地转置

7

这个问题类似于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}

我知道可以通过创建一个新的数组来实现，但我想知道如何像先前提到的问题的解决方案一样在原地完成。

- Julian Mann

你知道进入函数的高度和宽度吗？如果不知道，有很多方法可以将其显示为矩形。 - Dan W

“相对简单”的方法使用O（M * N）的辅助空间，即使它们在原地交换元素。 - harold

是的，我事先知道高度和宽度。 - Julian Mann

“从RGB值数组中切片平面（原地）的算法”与此非常相似。 - Evgeny Kluev

4

有一篇详细的维基百科文章介绍就地矩阵转置。链接为http://en.wikipedia.org/wiki/In-place_matrix_transposition。 - Ted Hopp

2个回答

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

我在这里为了清晰度而牺牲了一些优化。如果你真的很注重节省内存但愿意付出计算成本，可以查看相关维基百科文章中的参考资料，使用更复杂的算法来避免位图。

- G-J

维基百科的文章很棒！谢谢。我会在尝试MSN的解决方案之后再尝试你的解决方案。 - Julian Mann

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MSN · Accepted Answer

一种简单的原地转置方式是从矩阵的后面开始将每个元素旋转到位。您只需要每次将一个单独的元素旋转到位，因此对于示例，从[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);
        }
    }
}