【稀疏矩阵转置】线性时间复杂度实现稀疏矩阵转置

╰+哭是因爲堅強的太久メ 2022-06-07 12:07 294阅读 0赞

Think:  
1知识点：线性时间复杂度实现稀疏矩阵转置  
2方法：  
（１）：通过三元组记录初始输入信息  
（２）：记录每一列的元素个数  
（３）：求得记录每一列的第一个元素应放置的转置三元组的位置  
（４）：通过（３）所得到的记录数组和初始输入时记录的三元组遍历转置稀疏矩阵即可

3反思：  
（１）：求解记录的是每一列的第一个元素应放置的转置三元组的位置，故遍历范围为\[1, nu\]而不是\[1, tu\]

例题：  
[SDUT——数据结构实验之数组三：快速转置][SDUT]

Problem Description  
转置运算是一种最简单的矩阵运算，对于一个m\*n的矩阵M( 1 = < m < = 10000,1 = < n < = 10000 )，它的转置矩阵T是一个n\*m的矩阵，且T( i , j )=M( j , i )。显然，一个稀疏矩阵的转置仍然是稀疏矩阵。你的任务是对给定一个m\*n的稀疏矩阵( m , n < = 10000 )，求该矩阵的转置矩阵并输出。矩阵M和转置后的矩阵T如下图示例所示。  
![这里写图片描述][SouthEast]  
稀疏矩阵M  
![这里写图片描述][SouthEast 1]  
稀疏矩阵T

Input  
连续输入多组数据，每组数据的第一行是三个整数mu, nu, tu(tu <= 50)，分别表示稀疏矩阵的行数、列数和矩阵中非零元素的个数，随后tu行输入稀疏矩阵的非零元素所在的行、列值和非零元素的值，同一行数据之间用空格间隔。(矩阵以行序为主序)

Output  
输出转置后的稀疏矩阵的三元组顺序表表示。

Example Input  
3 5 5  
1 2 14  
1 5 -5  
2 2 -7  
3 1 36  
3 4 28

Example Output  
1 3 36  
2 1 14  
2 2 -7  
4 3 28  
5 1 -5

Hint

Author  
xam

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Node{
        int x, y, num;
    }node1[104], node2[104];
    
    int book[14014], cpot[14014];
    
    int main(){
        int mu, nu, tu;
        while(~scanf("%d %d %d", &mu, &nu, &tu)){
            memset(book, 0, sizeof(book));
            for(int i = 1; i <= tu; i++){
                scanf("%d %d %d", &node1[i].x, &node1[i].y, &node1[i].num);
                book[node1[i].y]++;
            }
            cpot[1] = 1;
            for(int i = 2; i <= nu; i++){
                cpot[i] = cpot[i-1] + book[i-1];
            }
            for(int i = 1; i <= tu; i++){
                int id = cpot[node1[i].y];
                node2[id].x = node1[i].y;
                node2[id].y = node1[i].x;
                node2[id].num = node1[i].num;
                cpot[node1[i].y]++;
            }
            for(int i = 1; i <= tu; i++){
                printf("%d %d %d\n", node2[i].x, node2[i].y, node2[i].num);
            }
        }
        return 0;
    }

[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2226/pid/3347
[SouthEast]: /images/20220607/a212b85d48624447b1422f66b82189c2.png
[SouthEast 1]: /images/20220607/abd843ba3b0e4d3fb5380e70f1d13292.png