转换一个不代表正方形的1维数组

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

实现此目的的一种方法是将原始矩阵的每个现有元素移动到新位置，注意首先拾取目标索引处的值，以便它也可以移动到新位置。对于任意 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

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