题目：用O(1)的空间实现矩阵的转置
为了方便，使用一维数组来分析。所谓矩阵转置，行变列，列变行。在转置的过程中，有的元素位置是不变的；对于变化位置的元素，要求O(1)空间完成，那么这些位置的变化一定是有着规律的。
举例，2×5的矩阵，A={0,1,2,3,4,5,6,7,8,9}；转置后为AT={0,5,1,6,2,7,3,8,4,9}，探索下标变化：
0->0
1->2->4->8->7->5->1
3->6->3
9->9
这些下标的变化是一些环，如果我们能找到这个环，对环做移动处理，就可以O(1)完成了。
现在的问题是，我们如何知道一个环是已经处理过的，仔细观察，如果一个环被处理过，那么总能找到一个它的后继是小于它的。例如，处理了前三个环的时候，当尝试找下标4打头的环时，一直找4的后继下标，会发现后继1是小于4的，我们就知道4是存在于一条已经处理过的环，跳过。
接下来的问题是如何找到当前元素下标的前驱和后继。先求下标i转置前的下标，即i的前驱，对于m×n的矩阵，转置后为n×m，则一维数组的第i个元素表示的行列为(i/m, i%m)，根据转置原理，那么这个元素在转置前的m×n矩阵中所表示的行列为(i%m, i/m)，那么i在转置前一维数组中的位置为j=(i%m)×n+(i/m)。同理，下标i转置后的位置j=(i%n)×m+(i/n)。
这样，前驱后继都可以求得，找到环就移动环的元素，如果已处理过则跳过，代码如下：
评论：个人觉得每条环总能找到一个它的后继是小于它的原因在于，每条环开始的第一个位置下标总是整条环中最小的，所以只有第一次能遍历权环并回到开始的点。而之所以每条环开始的第一个位置下标最小，是因为整个数组的遍历过程是从小到大，可以保证比每条环开始的位置小的位置都被遍历过了。
int Pre(int index, int m, int n) // 求前驱
{
return (index % m) * n + (index / m);
}
int Next(int index, int m, int n) // 求后继
{
return (index % n) * m + (index / n);
}
void move(int * a, int i, int m, int n) // 处理环
{
int curVal = a[i];
int cur = i;
int pre = Pre(i,m,n);
while(i != pre)
{
a[cur] = a[pre];
cur = pre;
pre = Pre(cur,m,n);
}
a[cur] = curVal;
}
void transpose(int *a, int m, int n) // 转置
{
for(int i = 0; i < m*n; ++i)
{
int next = Next(i,m,n);
while(i < next) // 若大于说明已处理过
{
next = Next(next,m,n);
}
if(next == i)
{
move(a,i,m,n);
}
}
}
int main()
{
int a[10] = {0,1,2,3,4,5,6,7,8,9};
for(int i = 0; i < 10; ++i)
{
printf("%d ",a[i]);
}
printf("\n");
transpose(a,2,5);
for(int i = 0; i < 10; ++i)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
转自：http://www.ahathinking.com/archives/217.html
更多：http://zhiqiang.org/blog/science/computer-science/another-perfect-shuffle-algorithm.html
http://space.itpub.net/67063/viewspace-169250