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]的大小

• 定义顺序为r1 x c2的一个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, ],]