32 ms C++ solution with map


  • 0
    D

    class Solution {
    public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
    if(A.size() == 0 || B.size() == 0 || B[0].size() == 0){
    return vector<vector<int>>();
    }
    int m = A.size(), n = B.size(), p = B[0].size();
    vector<vector<int>> C(m,vector<int>(p,0));
    unordered_map<int, vector<pair<int,int>> > Amap;
    unordered_map<int, vector<pair<int,int>> > Bmap;
    for(int i = 0; i < m; i++){
    for(int k = 0; k < n; k++){
    if(A[i][k]){
    Amap[k].push_back(make_pair(i,A[i][k]));
    }
    }
    }
    for(int k = 0; k < n; k++){
    for(int j = 0; j < p; j++){
    if(B[k][j]){
    Bmap[k].push_back(make_pair(j,B[k][j]));
    }
    }
    }
    for(pair<int, vector<pair<int,int>>> p : Amap){
    if(Bmap.count(p.first)){
    for(pair<int,int> a: p.second){
    for(pair<int,int> b : Bmap[p.first]){
    C[a.first][b.first] += a.second*b.second;
    }
    }
    }
    }
    return C;
    }
    };'''


Log in to reply
 

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