Standard hash table solution 36ms in C++


  • 3
    T
    typedef pair<pair<int,int>,int> pos_val;
    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            if(A.empty()||A[0].empty()||B[0].empty()) return vector<vector<int>>();
            vector<pos_val> map_A,map_B; //store nonzero values of A and B
            int n=A.size(), m=B[0].size(),mid=B.size();
            vector<vector<int>> C(n,vector<int>(m,0));
            for(int i=0;i<n;++i){
                for(int j=0;j<mid;++j){
                    if(A[i][j]!=0){
                        pos_val tmp(pair<int,int>(i,j),A[i][j]);
                        map_A.push_back(tmp);}
                    }
              }
             for(int i=0;i<mid;++i){
                for(int j=0;j<m;++j){
                    if(B[i][j]!=0){
                        pos_val tmp(pair<int,int>(i,j),B[i][j]);
                        map_B.push_back(tmp);}
                    }
              }
            for(int i=0;i<map_A.size();++i){
                for(int j=0;j<map_B.size();++j){
                    if(map_A[i].first.second==map_B[j].first.first)
                       C[map_A[i].first.first][map_B[j].first.second]+=map_A[i].second*map_B[j].second;
                }
            }
            
            return C;
            
        }
    };

  • 1
    X

    @touzi

    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
          if ( A.empty() || B.empty() ) return vector<vector<int>>();
          vector< pair< pair<int, int>, int > > mapA, mapB;
          int n = A.size(), m = A[0].size(), p = B[0].size();
          for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
              if ( A[i][j] != 0 )
                mapA.push_back( { {i, j}, A[i][j] } );
            }
          }
          for (int k = 0; k < p; k++) {
            for (int j = 0; j < m; j++) {
              if ( B[j][k] != 0 )
                mapB.push_back( { {j, k}, B[j][k] } );
            }
          }
          vector<vector<int>> res(n, vector<int>(p, 0));
          for (auto ha: mapA) {
            for (auto hb: mapB) {
              if (ha.first.second == hb.first.first)
                res[ha.first.first][hb.first.second] += ha.second * hb.second;
            }
          }
          return res;
        }
    };

  • 0
    E

    @touzi said in Standard hash table solution 36ms in C++:

    typedef pair<pair<int,int>,int> pos_val;
    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            if(A.empty()||A[0].empty()||B[0].empty()) return vector<vector<int>>();
            vector<pos_val> map_A,map_B; //store nonzero values of A and B
            int n=A.size(), m=B[0].size(),mid=B.size();
            vector<vector<int>> C(n,vector<int>(m,0));
            for(int i=0;i<n;++i){
                for(int j=0;j<mid;++j){
                    if(A[i][j]!=0){
                        pos_val tmp(pair<int,int>(i,j),A[i][j]);
                        map_A.push_back(tmp);}
                    }
              }
             for(int i=0;i<mid;++i){
                for(int j=0;j<m;++j){
                    if(B[i][j]!=0){
                        pos_val tmp(pair<int,int>(i,j),B[i][j]);
                        map_B.push_back(tmp);}
                    }
              }
            for(int i=0;i<map_A.size();++i){
                for(int j=0;j<map_B.size();++j){
                    if(map_A[i].first.second==map_B[j].first.first)
                       C[map_A[i].first.first][map_B[j].first.second]+=map_A[i].second*map_B[j].second;
                }
            }
            
            return C;
            
        }
    };
    

    Can someone explain how this is better than simply doing a check whether A[i][k] or B[k][J] is 0 in the innermost iteration of loops in the brute-force (traditional) matrix multiplication method?

      for(int i=0;i<map_A.size();++i){
                for(int j=0;j<map_B.size();++j){
                    if(map_A[i].first.second==map_B[j].first.first)
                       C[map_A[i].first.first][map_B[j].first.second]+=map_A[i].second*map_B[j].second;
                }
            }
    

    This loop-nesting itself has worse complexity than brute-force approach. The size of map_A and map_B are n * mid and mid * m respectively, so the if statement within the loop itself is called n * m * mid * mid times and can have upto

    n*m*mid*mid times 
    

    many multiplications, which is worse than O(nm mid) multiplications in brute-force.


Log in to reply
 

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