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 सरणी रेट को परिभाषित करें

• एक सरणी को परिभाषित करें 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 :=विरल का पहला तत्व[i, j]

      • यदि B[x, k] 0 के बराबर नहीं है, तो -

        • ret[i, k] :=ret[i, k] + sparseA का दूसरा तत्व [i, j] * B[x, k]

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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