C++でのスパース行列の乗算

2つの行列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を1つ定義します。

• ペアの配列sparseA[r1]を定義します

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • A [i、j]が0に等しくない場合、-

      • sparseA [i]

        の最後に{j、A [i、j]}を挿入します

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • 初期化k：=0の場合、k

      • x：=sparseA [i、j]

        の最初の要素

      • B [x、k]が0に等しくない場合、-

        • ret [i、k]：=ret [i、k] + sparseA [i、j]の2番目の要素* B [x、k]

• 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, ],]