C++ Straight Forward method


  • 9
    T

    First scan the two matrix to find the index of non-zeros entries, push these entries to vector.
    When computing the result, just consider

    1. when index equal, then increment both index

    2. otherwise increment smaller index

      vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {

       int am = A.size();//2
       int bm = B.size();//3
       //if(!am || !bm)
       //    return result;
       int an = A[0].size();//3
       int bn = B[0].size();//3 2*3 3*3 => 2*3
       vector<vector<int>> result(am,vector<int>(bn,0));
       vector<vector<int>> A_non_zero(am);
       vector<vector<int>> B_non_zero(bn);
       //an == bm
       for(int i=0;i<am;i++)
           for(int j=0;j<an;j++)
               if(A[i][j])A_non_zero[i].push_back(j);
               
       for(int j=0;j<bn;j++)
           for(int i=0;i<bm;i++)
               if(B[i][j])B_non_zero[j].push_back(i);
       
       for(int i=0;i<am;i++)
           for(int j=0;j<bn;j++){
               int m=0,n=0;
               while(m<A_non_zero[i].size() && n<B_non_zero[j].size()){
                   int idx_A = A_non_zero[i][m];
                   int idx_B = B_non_zero[j][n];
                   if(idx_A == idx_B){
                       result[i][j]+= (A[i][idx_A]*B[idx_B][j]);
                       m++;
                       n++;
                   }
                   else if(idx_A > idx_B)
                       n++;
                   else 
                       m++;
               }
           }
       return result;
      
    }

  • 0
    I

    Thanks! Here's a solution with one hash table for B alone.

    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            vector<vector<int>> out(A.size(), vector<int>(B[0].size(), 0));
            unordered_map<int, vector<int>> BNonZeroIndexes;
            
           for(int i = 0; i < B.size(); i++) {
                BNonZeroIndexes[i] = {};
                for(int k = 0; k < B[0].size(); k++) {
                   if(B[i][k])  BNonZeroIndexes[i].push_back(k);
                }
            }
            
            
            for(int i = 0; i < A.size(); i++) {
                 for(int k = 0; k < A[0].size(); k++) {
                    if(A[i][k] != 0) {
                        for(int j : BNonZeroIndexes[k]) { //In Row K, Iterate only over indexes that has non-zero values.
                             out[i][j] += A[i][k] * B[k][j];
                        }
                    }
                }
            }
            
            return out;
        }
    };
    

  • 0
    Z

    One vector<vector<int>> for B will be sufficient and better than hash table.

    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            int m = A.size(), n = A[0].size(), p = B[0].size();
            vector<vector<int>> mtxB(n, vector<int>());
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < p; ++j) {
                    if (B[i][j] != 0) mtxB[i].push_back(j);
                }
            }
            vector<vector<int>> ans(m, vector<int>(p, 0));
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (A[i][j] != 0) {
                        for (int k: mtxB[j]) {
                            ans[i][k] += A[i][j]*B[j][k];
                        }
                    }
                }
            }
            return ans;
        }
    };
    

    We can further optimize the code using only one vector<int>. See below.

    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            int m = A.size(), n = A[0].size(), p = B[0].size();
            vector<vector<int>> ans(m, vector<int>(p, 0));
            for (int j = 0; j < n; ++j) {
                // working on colume j of A and row j of B
                vector<int> rowB;
                for (int i = 0; i < p; ++i)
                    if (B[j][i]) rowB.push_back(i);
                for (int i = 0; i < m; ++i) {
                    if (A[i][j]) {
                        for (int k: rowB) {
                            ans[i][k] += A[i][j]*B[j][k];
                        }
                    }
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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