稀疏矩阵的倒置几种做法

蔚落 2023-07-25 12:43 61阅读 0赞

## 题目 ##

18722 稀疏矩阵的运算  
时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: 不限定  
Description  
稀疏矩阵的压缩存储原则：只存矩阵的行列数和每个非零元的行列下标及其值。  
例如下图的矩阵M由行列数（6,7）和三元组表\{(1,2,12), (1,3,9), (3,1,-3),(3,6,14),(4,3,24),(5,2,18), (6,1,15), (6,4,-7) \}唯一确定。  
问题描述：已知一个稀疏矩阵的三元组表，使用快速转置算法求其转置矩阵的三元组表，三元组表要按行优先的方式存储。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1Mjc2NQ_size_16_color_FFFFFF_t_70]

## 输入格式 ##

第一行三个整数n,m,k。n,m代表矩阵A的行列数（0<=n,m<=1000000）,k为三元组表中元素的个数。  
此后为k行，每行3个整数a，b，c，分别代表元素的行号，列号和值。数据确保按行优先给出。（0<=k<=10000）

## 输出格式 ##

输出为k行，即转置矩阵的三元组表，三元组表要按行优先显示。

## 输入样例 ##

6 7 8  
1 2 12  
1 3 9  
3 1 -3  
3 6 14  
4 3 24  
5 2 18  
6 1 15  
6 4 -7

## 输出样例 ##

1 3 -3  
1 6 15  
2 1 12  
2 5 18  
3 1 9  
3 4 24  
4 6 -7  
6 3 14

## 解题思路： ##

一、最简单最直接的当然是暴力求解啦。那么如何暴力呢？我们知道三元组是以行优先的方式来存储矩阵的。同时在三元组中，我们还可以知道同一列的元素，行小的在前面。那么我们在进行倒置的时候无非是要将某个点的行列交换，而交换后要确保以行优先的方式存储。因此我们可以对三元组进行暴力扫描。第一次扫描列为1的情况，第二次扫描列为2的情况，直到列为m。每次扫描的时候就将扫描到的元素交换i，j再存储到另外一个数组。对于列相同的行不相同的那些元素，可知行小的在前面，交换i,j后可以知道列小的还是在前面，因此这是完全正确的。时间复杂度为O(k\*m)。

#include<iostream>
    using namespace std;
    struct node
    { 
    	int x,y,val;
    }a[1000005],b[100005];
    int main()
    { 
    	int n,m,k,p=1;
    	cin>>n>>m>>k;
    	for(int i=1;i<=k;i++)
    	cin>>a[i].x>>a[i].y>>a[i].val;
    	for(int j=1;j<=m;j++)//直接暴力,复杂度k*m 
    	for(int l=1;l<=k;l++)// 
    	{ 
    		if(a[l].y==j)
    		{ 
    			b[p].x=a[l].y;
    			b[p].y=a[l].x;
    			b[p].val=a[l].val;
    			p++;
    		}
    		
    	 }
    	 for(int i=1;i<=k;i++)
    	 cout<<b[i].x<<' '<<b[i].y<<' '<<b[i].val<<endl;
    	 return 0; 
    }

二、另外一个方法也可以说是暴力，但是这方法暴力中有巧妙。  
先将三元组输入结构体数组a,然后再将a中的元素赋值给结构体数组b,赋值时将a成员的i赋给b成员的 j ,将a成员的 j 赋给b成员的 i ;；其余原封不动。然后利用STL的sort()自定义规则将结构体数组b进行排序，然后输出就完事儿了。

#include<iostream>
    #include<algorithm>
    using namespace std;
    struct node
    { 
    	int x,y,val;
     }a[1000005],b[1000005];
     bool cmp(struct node a1,struct node a2)
     { 
     	if(a1.x!=a2.x)
     	return a1.x<a2.x;
     	else 
     	return a1.y<a2.y;
     }
     int main()//216ms 
     { 
     	int n,m,k;
     	cin>>n>>m>>k;
     	for(int i=1;i<=k;i++)
     	cin>>a[i].x>>a[i].y>>a[i].val;
     	for(int i=1;i<=k;i++)
     	{ 
     			b[i].x=a[i].y;
     			b[i].y=a[i].x;
     			b[i].val=a[i].val;
    	 }
    	 sort(b+1,b+1+k,cmp);
    	 for(int j=1;j<=k;j++)
    	 cout<<b[j].x<<' '<<b[j].y<<' '<<b[j].val<<endl;
    	 return 0;
     }

三、这个是教材的方法，名为快速转置算法(确实很快）。  
三元组：  
**6 7 8  
1 2 12  
1 3 9  
3 1 -3  
3 6 14  
4 3 24  
5 2 18  
6 1 15  
6 4 -7**  
首先创建一个数组来记录每一列共有共有几个元素。  
其次再创建一个数组记录每一列最开始时的下标，最开始的下标代表了首次遇到该列元素是需要存到另外一个数组的相应位置。然后再对此数组的相应值加一，代表下次再遇到该列的元素时，存到另一个数组的相应位置。  
`(int i=1;i<=k;i++)//对不同列进行计数 num[a[i].y]++; copt[1]=1; for(int i=2;i<=m;i++)//累加 copt[i]=copt[i-1]+num[i-1];`  
第一列的开始下标就是1,而第二列的开始下标就是第一列的开始下标加上第一列元素的个数，其余的以此类推。  
最后也是利用一个新的结构体数组进行赋值操作。  
从1到K对K个数进行扫描，将该数相应的赋值到结构数组的相应位置即可。

#include<iostream>//260ms
    using namespace std;
    struct node 
    { 
    	int  x,y,val;
     } a[1000005],b[1000005];
    int num[1000005];
    int copt[1000005];
     int main()
     { 
     	int n,m,k;
     	cin>>n>>m>>k;
     	for(int i=1;i<=k;i++)
     	cin>>a[i].x>>a[i].y>>a[i].val;
     	for(int i=1;i<=k;i++)//对不同列进行计数 
     	num[a[i].y]++;
     	copt[1]=1;
     	for(int i=2;i<=m;i++)//累加 
     	copt[i]=copt[i-1]+num[i-1];
     	for(int i=1;i<=k;i++)
     	{ 
     		int q=a[i].y;
     		b[copt[q]++]={ a[i].y,a[i].x,a[i].val};
    	 }
     	for(int i=1;i<=k;i++)
     	cout<<b[i].x<<' '<<b[i].y<<' '<<b[i].val<<endl;
     	return 0;
     }

完…

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1Mjc2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/694ad3fdc25345b4af4d69ae0cff8c7a.png