存档

文章标签 ‘矩阵原地转置’

矩阵转置 O(1)空间

2013年7月12日 8 条评论

---

题目:用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)。

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

阅读全文...