调换一个1维数组，不代表正方形
这个问题与此类似，但代替一个代表正方形的数组，我需要转置一个矩形数组。
所以，给定一个宽度：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}
我知道如何做一个新的数组，但我想知道如何做到这一点，就像前面提到的问题的解决方案。
做到这一点的一种方法是将原始矩阵中的每个现有元素移动到新的位置，注意首先在目标索引处拾取值，以便它也可以移动到新的位置。 对于任意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
我在这里牺牲了一些优化。 有可能使用更复杂的算法来避免位图 - 如果您真的非常重视以计算为代价来节省内存，请参阅相关维基百科文章中的参考资料。
转位的一种简单方法是将每个元素从矩阵的后面开始旋转到位。 您只需要一次将单个元素旋转到位，例如，从[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
一个元素的旋转实际上是没有操作的，但是这个进程导致了一个非常简单的算法（在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);
}
}
}
上一篇: Transpose a 1 dimensional array, that does not represent a square, in place
下一篇: Delphi XE2: Invisible Firemonkey controls in VirtualBox