C++ Solution using Hash Set


  • 0
    Y
    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            vector<vector<int>> ans;
            if(!A.size() || !B.size())
                return ans;
            int n = A.size(), m = B[0].size(), m1 = A[0].size(), n1 = B.size();
            ans.resize(n);
            for(int i = 0; i < n; ++ i){
                vector<int> tmp(m);
                ans[i] = tmp;
            }
            
            vector<unordered_set<int>> mtx1(n), mtx2(m);
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < m1; ++ j){
                    if(A[i][j]){
                        mtx1[i].insert(j);
                    }
                }
            }
            for(int i = 0; i < m; ++ i){
                for(int j = 0; j < n1; ++ j){
                    if(B[j][i]){
                        mtx2[i].insert(j);
                    }
                }
            }
            
            for(int i = 0; i < n; ++ i){
                if(!mtx1[i].size())
                    continue;
                for(int j = 0; j < m; ++ j){
                    int cnt = 0;
                    if(!mtx2[j].size())
                        continue;
                    unordered_set<int>::iterator it = mtx1[i].begin();
                    for(; it != mtx1[i].end(); ++ it){
                        if(mtx2[j].find(*it) != mtx2[j].end())
                            cnt += A[i][*it]*B[*it][j];
                    }
                    ans[i][j] = cnt;
                }
            }
            
            return ans;
        }
    };

  • 0
    Z

    I don’t think you will need the hash set. Just using vector<vector<int>> seems OK.


  • 0
    Y

    Exactly, just used the kind of data structure u r familiar with.


Log in to reply
 

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