矩阵转置 O(1)空间

本文主要是介绍矩阵转置 O(1)空间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：用O(1)的空间实现矩阵的转置

另外一篇文章：http://www.qushichao.com/archives/47.html

为了方便，使用一维数组来分析。所谓矩阵转置，行变列，列变行。在转置的过程中，有的元素位置是不变的；对于变化位置的元素，要求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)。

（1）前驱：由转置后的坐标求转置前的坐标，m*n转置后是n*m，则转置后的坐标为(i/n,i%n),则转置前坐标为：(i%n,i/n)  ==>  转置前的坐标为 (i%n)×m+(i/n)

（2）后继：由当前坐标求转置后的坐标，当前坐标为(i/m, i%m)，则转置后的坐标为(i%m, i/m),则转置后的位置为：

(i%m)*n+i/m

这样，前驱后继都可以求得，找到环就移动环的元素，如果已处理过则跳过，代码如下:

#include <cstdio>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");getchar();return 0;
}

这篇关于矩阵转置 O(1)空间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---