C++ 48ms solution or sparse matrix multiplication


  • 0
    C
    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            
            vector<vector<int>> res;
            int r1,c1,r2,c2;
            
            r1=A.size();
            r2=B.size();
            if(r1==0||r2==0) return res;
            
            c1=A[0].size(); 
            c2=B[0].size();
            if(c1==0||c2==0) return res;
            
            vector<bool> Ab(r1, false);
            vector<bool> Bb(c2, false);
            for(int i=0; i<r1; i++){
                for (int j=0; j<c1; j++){
                    if (A[i][j]){
                        Ab[i]=true;
                        break;
                    }
                }
            }
            for(int i=0; i<c2; i++){
                for (int j=0; j<r2; j++){
                    if (B[i][j]){
                        Bb[i]=true;
                        break;
                    }
                }
            }
            
            vector<int> row;
            int node=0;
            for(int i=0; i<r1; i++){
                if (!Ab[i]){
                    row.assign(c2, 0);
                    res.push_back(row);
                    continue;
                }
                row.clear();
                for (int k=0; k<c2;k++){
                    if (!Bb[k]){
                        row.push_back(0);
                        continue;
                    }
                    node = 0;
                    for (int j=0; j<c1; j++){
                        node+=A[i][j]*B[j][k];
                    }
                    row.push_back(node);
                }
                res.push_back(row);
            }    
        }
    };`enter code here`

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.