问题 1753 --算法5-2:稀疏矩阵快速转置

1753: 算法5-2:稀疏矩阵快速转置

时间限制: 1 Sec  内存限制: 32 MB
提交: 206  解决: 92
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][68kb]

题目描述

稀疏矩阵的存储不宜用二维数组存储每个元素,那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零元素。这个一维数组的元素类型是一个三元组,由非零元素在该稀疏矩阵中的位置(行号和列号对)以及该元组的值构成。
而矩阵转置就是将矩阵行和列上的元素对换。参考算法5.1中的具体做法,令mu和nu分别代表稀疏矩阵的行数和列数,不难发现其时间复杂度为O(mu×nu)。而当非零元的个数tu与mu×nu同数量级时,算法5.1的时间复杂度将上升至O(mu×nu2)。因此,需要采用快速的稀疏矩阵转置算法。
现在就请你实现一个快速的对稀疏矩阵进行转置的算法。以下是稀疏矩阵快速转置的算法描述:

输入

输入的第一行是两个整数r和c(r<200, c<200, r*c <= 12500),分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行,每行有c个整数,用空格隔开,表示这个稀疏矩阵的各个元素。

输出

输出为读入的稀疏矩阵的转置矩阵。输出共有c行,每行有r个整数,每个整数后输出一个空格。请注意行尾输出换行。

样例输入

6 7
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0

样例输出

0 0 -3 0 0 15 
12 0 0 0 18 0 
9 0 0 24 0 0 
0 0 0 0 0 -7 
0 0 0 0 0 0 
0 0 14 0 0 0 
0 0 0 0 0 0 

提示

提示:

这个算法仅比算法5.1多用了两个辅助向量。对于这个算法的时间复杂度,不难发现算法中有4个并列的单循环,循环次数分别为nu和tu,因而总的时间复杂度为O(nu+tu)。而当稀疏矩阵的非零元个数tu和mu×nu的数量级相同时,其时间复杂度为O(mu×nu),与经典算法的时间复杂度相同。

请注意理解为什么转置算法中,以列从小到大来进行转置。实际上只需一个循环就能够完成转置而不需将列从小到大来处理,转置后的矩阵虽然内容正确,但元素的顺序却发生了变化,以至于在后续的各种处理操作中会增加复杂度。而在本题中,如果不按照列从小到大的顺序处理将导致输出困难,大大增加输出的复杂度。

总结:

稀疏矩阵是矩阵应用中很重要的一部分,由于其元素稀疏的特殊性质,我们可以得到比传统矩阵算法更快速的特殊算法。这也将会在本章后面的题目中得到体现。

来源

[提交][状态]