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]] होगा:

समाधान दृष्टिकोण

स्पार्स मैट्रिक्स प्रतिनिधित्व का उपयोग करके केवल गैर-शून्य तत्वों को प्रोसेस करें:

1. r1 := A का आकार, r2 := B का आकार
2. c1 := A[0] का आकार, c2 := B[0] का आकार
3. क्रम r1 x c2 की 2D सरणी ret परिभाषित करें
4. पेयर्स की सरणी sparseA[r1] परिभाषित करें
5. i को 0 से r1-1 तक:
   • j को 0 से c1-1 तक:
     • यदि A[i][j] != 0, तो {j, A[i][j]} को sparseA[i] में जोड़ें
6. i को 0 से r1-1 तक:
   • sparseA[i] के प्रत्येक पेयर के लिए:
     • k को 0 से c2-1 तक:
       • x := पेयर का पहला तत्व (स्तंभ सूचकांक)
       • यदि B[x][k] != 0, तो ret[i][k] += पेयर का दूसरा तत्व * B[x][k]
7. ret लौटाएं

C++ कार्यान्वयन

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