C ++中的稀疏矩阵乘法
假设我们有两个矩阵A和B，我们必须找到AB的结果。我们可以假设A的列号等于B的行号。
因此，如果输入像[[1,0,0]，[-1,0,3]][[7,0,0]，[0,0,0]，[0,0,1]]，
那么输出将是[[7,0,0]，[-7,0,3]]
为了解决这个问题，我们将遵循以下步骤-
r1：=A的大小，r2：=B的大小
c1：=A[0]的大小，c2：=B[0]的大小
定义顺序为r1xc2的一个2D数组ret
定义成对的数组sparseA[r1]
对于初始化i：=0，当i<r1时，更新（将i增加1），执行-
如果A[i，j]不等于0，则-
在sparseA[i]的末尾插入{j，A[i，j]}
对于初始化j：=0，当j<c1时，更新（将j增加1），执行-
对于初始化i：=0，当i<r1时，更新（将i增加1），执行-
对于初始化k：=0，当k<c2时，更新（将k增加1），-
ret[i，k]：=ret[i，k]+sparseA[i，j]*B[x，k]的第二个元素
x：=sparseA[i，j]的第一个元素
如果B[x，k]不等于0，则-
对于初始化j：=0，当j<sparseA[i]的大小时，更新（将j增加1），执行-
返回ret
例
让我们看下面的实现以更好地理解-
class Solution {
public:
vector<vector<int<> multiply(vector<vector<int<>& A, vector<vector<int<>& B) {
int r1 = A.size();
int r2 = B.size();
int c1 = A[0].size();
int c2 = B[0].size();
vector < vector <int< > ret(r1, vector <int< (c2));
vector < pair <int, int> > sparseA[r1];
for(int i = 0; i < r1; i++){
for(int j = 0; j < c1; j++){
if(A[i][j] != 0)sparseA[i].push_back({j, A[i][j]});
}
}
for(int i = 0; i < r1; i++){
for(int j = 0; j < sparseA[i].size(); j++){
for(int k = 0; k < c2; k++){
int x = sparseA[i][j].first;
if(B[x][k] != 0){
ret[i][k] += sparseA[i][j].second * B[x][k];
}
}
}
}
return ret;
}
};输入值
{{1,0,0},{-1,0,3}},{{7,0,0},{0,0,0},{0,0,1}}输出结果
[[7, 0, 0, ],[-7, 0, 3, ],]