存档

2013年7月 的存档

矩阵转置 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)。

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

阅读全文...

此刻,感恩

2013年7月12日 6 条评论

---

过去这一年是不怎么好过的一年,经历了很多事,一年中碰到的事情感觉比整个大学遇到的还要多,很庆幸现在都成为过去,自己也对即将开启的新生活充满期待。

这一年中,得到了太多人的帮助,我真心很感恩,感谢在我困难时那些伸出援手的挚友,感谢在我窘迫时那些能够陪伴我的人,感谢在我几近绝望时帮我创造机会以及给予我机会的人,感谢一直给我鼓励打气的朋友。

在以后的人生中,我也会努力去为身边需要帮助的人做我能做的事,在我有能力为别人创造机会的时候我也会尽力,希望将我得到的正能量也传递给需要正能量的人。

此刻,感恩。

这一年,还要感谢自己,感谢曾经倔强的自己,感谢一直没放弃的自己。有时候我在想,应该对过去的一年好好总结,想来想去我觉得没什么总结的,这些都是要经历的,只有经历才会增加厚度,除了感恩,没有其他,埋在心底,继续努力吧。

此刻,我更加坚定:现在的碎碎片片要虔诚地对待,总有一天它会成为你做成一件事情的一针一线!就像乔布斯说的,你所学的一切终究会用到,总有一天它们会串联成一条线。我想,到那一天,我们都会感谢曾经认真的自己。 阅读全文...

分类: 生活随笔 标签: ,