[C++] Using hash tables (unordered_maps)


  • 0
    vector<vector<int>> multiply(vector<vector<int>> &A, vector<vector<int>> &B) {
        int m = A.size(), n = m ? A[0].size() : 0, p = n ? B[0].size() : 0;
        if (!m || !n || !p) return {};
            
        unordered_map<int, list<pair<int, int>>> htA, htB;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (A[i][j]) 
                    htA[i].emplace_back(j, A[i][j]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < p; j++)
                if (B[i][j]) 
                    htB[j].emplace_back(i, B[i][j]);
            
        vector<vector<int>> res (m, vector<int> (p, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < p; j++) {
                auto foundA = htA.find(i), foundB = htB.find(j);
                if (foundA != htA.end() && foundB != htB.end()) {
                    auto l1 = foundA->second, l2 = foundB->second;
                    auto it1 = l1.begin(), it2 = l2.begin();
                    while (it1 != l1.end() && it2 != l2.end()) {
                        if (it1->first == it2->first) {
                            res[i][j] += it1->second * it2->second;
                            it1++; it2++;
                        }
                        else if (it1->first < it2->first) it1++;
                        else it2++;
                    }
                }
            }
        }
        return res;
    }
    

Log in to reply
 

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