首页 > 笔试面试题, 算法 数据结构 > 矩阵转置 O(1)空间

矩阵转置 O(1)空间

2013年7月12日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

题目:用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;
}

(全文完)

  • lmmandwxy

    mark.明词说明ls...

  • wintop

    哪个服务商的服务器啊 速度很快啊!

    • Yx.Ac

      @wintop 游子主机,你搜一下,PS:用香港主机国内看挺快的

  • Moon

    好吧,原来是这样囧。。。

  • Moon

    @Moon
    还有师兄,我的校园网IP真的被你屏蔽了- -。。。

  • Moon

    我个人觉得每条环总能找到一个它的后继是小于它的原因在于,每条环开始的第一个位置下标总是整条环中最小的,所以只有第一次能遍历权环并回到开始的点。而之所以每条环开始的第一个位置下标最小,是因为整个数组的遍历过程是从小到大,可以保证比每条环开始的位置小的位置都被遍历过了。

    • Yx.Ac

      @Moon 你理解的对,哈;PS:我没有设置IP屏蔽呀,个人认为你IP被屏蔽纯属平时坏事干的太多,应该检讨了,咳咳

    • guess

      其实,为了确认每个位置是否被换过,可以不用在后继中找是否有小于它的位置,我们可以把已经操作过的位置在原数字上做一个标记。至于怎么标记,可以有很多种方法。