Dotcpp  >  编程题库  >  数据结构-稀疏矩阵快速转置
题目 1693:

数据结构-稀疏矩阵快速转置

时间限制: 3s 内存限制: 96MB 提交: 232 解决: 123

题目描述

稀疏矩阵的存储不宜用二维数组存储每个元素,那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零元素。这个一维数组的元素类型是一个三元组,由非零元素在该稀疏矩阵中的位置(行号和列号对)以及该元组的值构成。
而矩阵转置就是将矩阵行和列上的元素对换。参考算法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 

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签

通过率

统 计